Soft-shelled turtles, or Trionychia, are an enigmatic and fascinating group due to their specific morphological features and ecological adaptations. Based on mitochondrial DNA (mtDNA) and/or nuclear markers, previous studies showed the incongruent phylogenetic topologies within Trionychia (e.g., the Palea and its closely related species). In order to resolve the equivocal relationships and obtain some "genome-level" common evolutionary characters of soft-shelled turtles, in this study, we assembled and annotated the complete mitochondrial genomes of Palea steindachneri and Pelodiscus axenaria, both naturally distributed in Asia. The sizes of the two mitochondrial genomes were 16,811 bp and 17,143 bp, respectively. Typical vertebrate animal mtDNA features were observed, such as the usual gene components and arrangements (37 genes with a non-coding control region) and the A + T biased nucleotide compositions on the light strand (61.5% and 62.7%, respectively). All conserved blocks common to the vertebrates control region except for the extended terminal associated sequences (ETAS2) were found in the two soft-shelled turtles. The ω ratio averaged over all sites of each protein-coding gene (PCG) was below 1, which indicated purifying selection at the gene-wide level. However, a positive selection site at the 350-codon position in the cytb gene was detected, as estimated by Bayes empirical Bayes (BEB) analysis. Compared with the gene subsets, the mitogenomes provided the most robust phylogenetic resolution. The monophyly of the clades Amydona, Gigantaesuarochelys, and Apalonia was well supported. Topology discrepancies were observed among different datasets (e.g., the positions of Lissemys and Palea), reflecting the heterogeneous phylogenetic signals in the soft-shelled turtle mitogenomes. Precise date estimation based on Bayesian relaxed clock analyses indicated that the crown group age of extant Trionychia was approximately 115.84 Ma (95% HPD: 91.33-142.18 Ma). Paleoclimate changes, especially the Eocene - Oligocene transition, could be responsible for the speciation in these groups. Our results reiterated the necessity and effectiveness of incorporating entire mitochondrial genomes to delineate phylogenetic relationships in chelonian phylogeny studies.