Diversification and speciation processes are influenced by intrinsic (ecological specialization, dispersal) and extrinsic (habitat structure and instability) factors, but the effect of ecological characteristics on dispersal is difficult to assess. This study uses mitochondrial control region sequences to investigate the population structure and demographic history of the endemic Lake Tanganyika cichlid Neolamprologus caudopunctatus with a preference for the rock-sand interface along two stretches of continuous, rocky shoreline, and across a sandy bay representing a potential dispersal barrier. Populations along uninterrupted habitat were not differentiated; whereas, the sandy bay separated two reciprocally monophyletic clades. The split between the two clades between 170,000 and 260,000 years BP coincides with a period of rising water level following a major lowstand, and indicates that clades remained isolated throughout subsequent lake level fluctuations. Low long-term effective population sizes were inferred from modest genetic diversity estimates, and may be due to recent population expansions starting from small population sizes 45,000-60,000 years BP. Comparisons with available data from specialized rock-dwelling species of the same area suggest that habitat structure and lake level fluctuations determine phylogeographic patterns on large scales, while fine-scale population structure and demography are modulated by species-specific ecologies.