Lake Tanganyika harbors the oldest and most diverse species flock of cichlid fish. Many species are subdivided into numerous genetically and phenotypically distinct populations. Their present distribution and genetic structure were shaped by a series of lake level fluctuations which caused cycles of isolation and admixis and promoted dispersal events. One of the best examples of this phenomenon is the genus Tropheus. We present a comprehensive mtDNA phylogeny based upon 365 individuals of 55 populations from all over Lake Tanganyika, which suggests an almost-contemporaneous origin of eight major mitochondrial lineages about 700 Ka ago. While the distribution of seven lineages is restricted to particular sections of the lake shore, one lineage was found to have a much more widespread distribution. This particular lineage is subdivided into four sublineages which seem to have originated from a single dispersal event about 400 Ka. By using a molecular clock estimate in combination with geological data we derived a hypothetical scenario for the colonization history of Tropheus. Thereby we show a high degree of concordance between major changes of the lake level in the recent history of Lake Tanganyika and three distinct diversification events in this genus.