The phylogenetic relationships of microhylid frogs are poorly understood. The first molecular phylogeny for continental African microhylids is presented, including representatives of all subfamilies, six of the eight genera, and the enigmatic hemisotid Hemisus. Mitochondrial 12S and 16S rRNA sequence data were analysed using parsimony, likelihood and Bayesian methods. Analyses of the data are consistent with the monophyly of all sampled subfamilies and genera. Hemisus does not nest within either brevicipitines or non-brevicipitines. It is possibly the sister group to brevicipitines, in which case brevicipitines might not be microhylids. Phrynomantis and Hoplophryne potentially group with non-African, non-brevicipitine microhylids, in agreement with recent morphological and molecular data. Within brevicipitines, Breviceps is recovered as the sister group to a clade of Callulina+Spelaeophryne+Probreviceps. The relationships among the genera within this latter clade are unclear, being sensitive to the method of analysis. Optimal trees suggest the Probreviceps macrodactylus subspecies complex might be paraphyletic with respect to P. uluguruensis, corroborating preliminary morphological studies indicating that P. m. rungwensis may be a distinct species. P. m. loveridgei may be paraphyletic with respect to P. m. macrodactylus, though this is not strongly supported. Some biogeographic hypotheses are examined in light of these findings.