Background: External segmentation and internal proglottization are important evolutionary characters of the Eucestoda. The monozoic caryophyllideans are considered the earliest diverging eucestodes based on partial mitochondrial genes and nuclear rDNA sequences, yet, there are currently no complete mitogenomes available. We have therefore sequenced the complete mitogenomes of three caryophyllideans, as well as the polyzoic Schyzocotyle acheilognathi, explored the phylogenetic relationships of eucestodes and compared the gene arrangements between unsegmented and segmented cestodes. Results: The circular mitogenome of Atractolytocestus huronensis was 15,130 bp, the longest sequence of all the available cestodes, 14,620 bp for Khawia sinensis, 14,011 bp for Breviscolex orientalis and 14,046 bp for Schyzocotyle acheilognathi. The A-T content of the three caryophyllideans was found to be lower than any other published mitogenome. Highly repetitive regions were detected among the non- coding regions (NCRs) of the four cestode species. The evolutionary relationship determined between the five orders (Caryophyllidea, Diphyllobothriidea, Bothriocephalidea, Proteocephalidea and Cyclophyllidea) is consistent with that expected from morphology and the large fragments of mtDNA when reconstructed using all 36 genes. Examination of the 54 mitogenomes from these five orders, revealed a unique arrangement for each order except for the Cyclophyllidea which had two types that were identical to that of the Diphyllobothriidea and the Proteocephalidea. When comparing gene order between the unsegmented and segmented cestodes, the segmented cestodes were found to have the lower similarities due to a long distance transposition event. All rearrangement events between the four arrangement categories took place at the junction of rrnS-tRNA(Arg) (P1) where NCRs are common. Conclusions: Highly repetitive regions are detected among NCRs of the four cestode species. A long distance transposition event is inferred between the unsegmented and segmented cestodes. Gene arrangements of Taeniidae and the rest of the families in the Cyclophyllidea are found be identical to those of the sister order Proteocephalidea and the relatively basal order Diphyllobothriidea, respectively.