The spectacularly diverse cichlid fish species flocks of the East African Rift Lakes have elicited much debate on the potential evolutionary mechanisms responsible for the origin of these adaptive radiations. An historical perspective on population structure may offer insights into the processes driving population differentiation and possibly speciation. Here, we examine mitochondrial DNA (mtDNA) sequence variation in two endemic species of rock-dwelling cichlids, Simochromis babaulti and S. diagramma, from Lake Tanganyika. Phylogeographic analyses were used to infer what factors might have been important in the genetic structuring of Simochromis populations. Patterns of mtDNA differentiation in Simochromis were compared to those of other rock-dwelling cichlids to distinguish between competing hypotheses concerning the processes underlying their evolution. In striking contrast to previous findings, populations of Simochromis, even those separated by up to 300 km, were found to share mitochondrial DNA haplotypes. There is no correspondence between mtDNA genealogies and the geographical distribution of populations. Only S. babaulti, but not S. diagramma was found to have a significant association between genetic and geographic distance. These phylogeographic patterns suggest that the evolutionary effects of abiotic and biotic factors shaping population genetic structure may differ substantially even among closely related species of rock-dwelling cichlids. Physical events and barriers to gene flow that are believed to have had a major impact on the geographical distribution and intralacustrine speciation of Tropheus do not seem to have equally strongly affected its close relative Simochromis. These findings emphasize that no single mechanism can be responsible for the formation of population structure, speciation, and the adaptive radiation of all cichlid fishes.