Determining the root of the anuran Tree of Life is still a contentious and open question in frog systematics. Two genera with disjunct distributions have been traditionally considered the most basal among extant frogs: Leiopelma, which is endemic to New Zealand, and Ascaphus, which lives in North America. However, their specific phylogenetic position is rather elusive because each genus shows many autapomorphies, and together they retain many symplesiomorphic characters. Therefore, several alternative hypotheses have been proposed regarding the relative phylogenetic position of both Leiopelma and Ascaphus. In order to distinguish among these competing phylogenetic hypotheses, we sequenced the complete mitochondrial (mt) genome of Leiopelma archeyi and used it along with previously reported frog mt genomes (including that of Ascaphus truei) to infer a robust phylogeny of major anuran lineages. The reconstructed maximum likelihood and Bayesian inference phylogenies recovered identical topology, which supports the sister group relationship of Ascaphus and Leiopelma, and the placement of this clade at the base of the anuran tree. Interestingly, the mt genome of L. archeyi displays a novel gene arrangement in frog mt genomes affecting the relative position of cytochrome b, trnT, NADH dehydrogenase subunit 6, trnE, and trnP genes. The tandem duplication-random loss model of gene order change explains the origin of this novel frog mt genome arrangement, which is convergent with others reported in some fishes and salamanders. These results, together with comparative data for other available vertebrate mt genomes, provide evidence that the 5' end of the control region is a hot spot for gene order rearrangement.