As part of an ongoing project to generate a mitochondrial database for terrestrial tortoises based on museum specimens, the complete mitochondrial genome sequences of 10 species and a approximately 14kb sequence from an eleventh species are reported. The sampling of the present study emphasizes Mediterranean tortoises (genus Testudo and their close relatives). Our new sequences are aligned, along with those of two testudinoid turtles from GenBank, Chrysemys picta and Mauremys reevesii, yielding an alignment of 14,858 positions, of which 3238 are parsimony informative. We develop a phylogenetic taxonomy for Testudo and related species based on well-supported, diagnosable clades. Several well-supported nodes are recovered, including the monophyly of a restricted Testudo, T. kleinmanni+T. marginata (the Chersus clade), and the placement of the enigmatic African pancake tortoise (Malacochersus tornieri) within the predominantly Palearctic greater Testudo group (Testudona tax. nov.). Despite the large amount of sequence reported, there is low statistical support for some nodes within Testudona and so we do not propose names for those groups. A preliminary and conservative estimation of divergence times implies a late Miocene diversification for the testudonan clade (6-10 million years ago), matching their first appearance in the fossil record. The multi-continental distribution of testudonan turtles can be explained by the establishment of permanent connections between Europe, Africa, and Asia at this time. The arrival of testudonan turtles to Africa occurred after one or more initial tortoise invasions gave rise to the diverse (>25 species) 'Geochelone complex.' Two unusual genomic features are reported for the mtDNA of one tortoise, M. tornieri (1) nad4 has a shift of reading frame that we suggest is resolved by translational frameshifting of the mRNA on the ribosome during protein synthesis and (2) there are two copies of the control region and trnF, with the latter having experienced multiple-nucleotide substitutions in a pattern suggesting that each is being maintained by selection.