Phylogenetic relationships of the East African caeciliid Boulengerula were reconstructed using 12S, 16S and cytb mitochondrial gene sequences for 32 samples from Kenya and Tanzania. The generally well-supported and resolved phylogeny displayed the following relationships among the five nominate species sampled: (B. boulengeri ((B. taitanus, B. niedeni), (B. changamwensis, B. uluguruensis))). This resolution supports a formerly proposed bipartition of the genus, and differs significantly from previous, morphological phylogenies. Our analyses identified genetic differences between several mtDNA clades that potentially represent undescribed species. If substantiated, the necessary taxonomic revision will have implications for conservation assessments that depend to an important extent upon sizes of distributions. Overall, there is a positive correlation between genetic and geographic distance among and within the main clades. The two lowland, coastal individuals sampled are nested within primarily montane clades. Dating analyses suggest some temporally congruent divergences in Boulengerula, but other divergences happened at different times and over a long period, perhaps extending back to the Oligocene/Eocene. Our results for Boulengerula suggest a role for relative long-term environmental stability in the origins of the Eastern Arc Mountains biodiversity hotspot.