Within the order Testudines, while phylogenetic analyses have been performed on the suborder Cryptodira with complete mitochondrial genomes (mitogenomes), mitogenomic information from another important suborder Pleurodira has been inadequate. In the present study, complete mitochondrial DNA (mtDNA) sequences of two chelid turtles Chelodina rugosa and Chelus fimbriata were firstly determined, the lengths of which were 16,582 and 16,661 bp respectively. As the typical vertebrate mitogenome, both mtDNAs consist of 13 protein coding genes, 2 ribosomal RNAs (rRNAs), 22 transfer RNAs (tRNAs), and a long noncoding region (control region, CR). However, the initiation sites for light-strand replication (O(L)), which has been identified in all reported Cryptodire mitogenomes, were not found in the putative position of the two chelid turtles and African helmeted turtle Pelomedusa subrufa. The results suggested that the absence of mitogenomic initiation sites (O(L)) could be a characteristic of Pleurodira. Phylogenetic relationships of chelid turtles and other turtles were reconstructed using the reported mitogenomes. Both maximum likelihood (ML) and Bayesian inference (BI) analyses suggested the monophyly of Pleurodira and Cryptodira as well as a sister group relationship between the two chelid turtles with strong statistical support. This phylogenetic framework was also utilized to estimate divergence dates among lineages using relaxed-clock methods combined with fossil evidence. Divergence estimates revealed that genus Chelodina diverged from genus Chelus in Late Cretaceous (~83 million years ago (mya)), and the time is consistent with the vicariance of the fragments which was caused by Gondwana split.