We used nuclear and mitochondrial DNA (mtDNA) sequences from specimens collected throughout Lake Tanganyika to clarify the evolutionary relationship between Lamprologus callipterus and Neolamprologus fasciatus. The nuclear data support the reciprocal monophyly of these two shell-breeding lamprologine cichlids. However, mtDNA sequences show that (i) L. callipterus includes two divergent and geographically disjunct (North-South) mtDNA lineages; and that (ii) N. fasciatus individuals cluster in a lineage sister group to the northern lineage of L. callipterus. The two mtDNA lineages of L. callipterus diverged c. 684 kya to 1.2 Ma, coinciding with a major water level low stand in Lake Tanganyika, which divided the lake into isolated sub-lakes. This suggests that the two mtDNA lineages originated as the result of the separation of L. callipterus populations in different sub-basins. The incongruent phylogenetic position of N. fasciatus can best be explained by an ancient unidirectional introgression from L. callipterus into N. fasciatus. Remarkably, our data indicate that this event resulted in the complete mtDNA replacement in N. fasciatus. Our data suggest that hybridization occurred soon after the divergence of the two L. callipterus mtDNA lineages, probably still during the water level low stand, and that subsequently the invading mtDNA lineage spread throughout the lake.