The evolutionary history of living African amphibians remains poorly understood. This study estimates the phylogeny within the frog genera Arthroleptis and Cardioglossa using approximately 2400 bases of mtDNA sequence data (12S, tRNA-Valine, and 16S genes) from half of the described species. Analyses are conducted using parsimony, maximum likelihood, and Bayesian methods. The effect of alignment on phylogeny estimation is explored by separately analyzing alignments generated with different gap costs and a consensus alignment. The consensus alignment results in species paraphyly, low nodal support, and incongruence with the results based on other alignments, which produced largely similar results. Most nodes in the phylogeny are highly supported, yet several topologies are inconsistent with previous hypotheses. The monophyly of Cardioglossa and of miniature species previously assigned to Schoutedenella was further examined using Templeton and Shimodaira–Hasegawa tests. Cardioglossa monophyly is rejected and C. aureoli is transferred to Arthroleptis. These tests do not reject Schoutedenella monophyly, but this hypothesis receives no support from non-parametric bootstrapping or Bayesian posterior probabilities. This phylogeny provides a framework for reconstructing historical biogeography and analyzing the evolution of body size and life history. Direct development and miniaturization appear at the base of Arthroleptis phylogeny concomitant with a range expansion from Central Africa to throughout most of sub-Saharan Africa.