Several lineages of cichlid fishes in the East African Great Lakes display stunning levels of morphological diversification. The rapid evolution of rock-dwelling polygynous mouthbrooders in Lake Malawi, for example, was in part ascribed to their allopatric distribution on disjunct stretches of rocky coast, where even short habitat discontinuities reduce gene flow effectively. However, as seen in other cichlids, ecological barriers do not always prevent gene flow, whereas genetic structure can develop along continuous habitat, and morphological diversification does not necessarily accompany genetic differentiation. The present study investigates the population structure of Variabilichromis moorii, a monogamous substrate-brooding lamprologine of rocky coasts in Lake Tanganyika, which occurs over about 1000 km of shoreline almost without phenotypic variation. Phylogeographic analyses of mitochondrial DNA sequences indicated that dispersal is infrequent and generally occurs between adjacent locations only. Exceptions to this pattern are closely related haplotypes from certain locations on opposite lakeshores, a phenomenon which has been observed in other species and is thought to reflect lake crossing along an underwater ridge in times of low water level. Genetic population differentiation, estimated from mitochondrial DNA and microsatellite data in six adjacent populations, was equally high across localities separated by sandy shores and along uninterrupted stretches of rocky shore. Our results suggest that ecological barriers are not required to induce philopatric behavior in Variabilichromis, and that morphological stasis persists in the face of high levels of neutral genetic differentiation.