Stenotopic specialization to a fragmented habitat promotes the evolution of genetic structure. It is not yet clear whether small-scale population structure generally translates into large-scale intraspecific divergence. In the present survey of mitochondrial genetic structure in the Lake Tanganyika endemic Altolamprologus (Teleostei, Cichlidae), a rock-dwelling cichlid genus comprising A. compressiceps and A. calvus, habitat-induced population fragmentation contrasts with weak phylogeographic structure and recent divergence among genetic clades. Low rates of dispersal, perhaps along gastropod shell beds that connect patches of rocky habitat, and periodic secondary contact during lake level fluctuations are apparently sufficient to maintain genetic connectivity within each of the two Altolamprologus species. The picture of genetic cohesion was interrupted by a single highly divergent haplotype clade in A. compressiceps restricted to the northern part of the lake. Comparisons between mitochondrial and nuclear phylogenetic reconstructions suggested that the divergent mitochondrial clade originated from ancient interspecific introgression. Finally, ‘isolation-with-migration’ models indicated that divergence between the two Altolamprologus species was recent (67–142 KYA) and proceeded with little if any gene flow. As in other rock-dwelling cichlids, recent population expansions were inferred in both Altolamprologus species, which may be connected with drastic lake level fluctuations.