BACKGROUND: The adaptive radiations of cichlid fishes in East Africa are well known for their spectacular diversity and their astonishingly fast rates of speciation. About 80% of all 2,500 cichlid species in East Africa, and virtually all cichlid species from Lakes Victoria (approximately 500 species) and Malawi (approximately 1,000 species) are haplochromines. Here, we present the most extensive phylogenetic and phylogeographic analysis so far that includes about 100 species and is based on about 2,000 bp of the mitochondrial DNA. RESULTS: Our analyses revealed that all haplochromine lineages are ultimately derived from Lake Tanganyika endemics. We find that the three most ancestral lineages of the haplochromines sensu lato are relatively species poor, albeit widely distributed in Africa, whereas a fourth newly defined lineage - the 'modern haplochromines' - contains an unparalleled diversity that makes up more than 7% of the worlds' approximately 25,000 teleost species. The modern haplochromines' ancestor, most likely a riverine generalist, repeatedly gave rise to similar ecomorphs now found in several of the species flocks. Also, the Tanganyikan Tropheini are derived from that riverine ancestor suggesting that they successfully re-colonized Lake Tanganyika and speciated in parallel to an already established cichlid adaptive radiation. In contrast to most other known examples of adaptive radiations, these generalist ancestors were derived from highly diverse and specialized endemics from Lake Tanganyika. A reconstruction of life-history traits revealed that in an ancestral lineage leading to the modern haplochromines the characteristic egg-spots on anal fins of male individuals evolved. CONCLUSION: We conclude that Lake Tanganyika is the geographic and genetic cradle of all haplochromine lineages. In the ancestors of the replicate adaptive radiations of the 'modern haplochromines', behavioral (maternal mouthbrooding), morphological (egg-spots) and sexually selected (color polymorphism) key-innovations arose. These might be - together with the ecological opportunity that the habitat diversity of the large lakes provides - responsible for their evolutionary success and their propensity for explosive speciation.