Lake Tanganyika, the oldest of the East African Great Lakes, harbors the ecologically, morphologically, and behaviorally most complex of all assemblages of cichlid fishes, consisting of about 200 described species. The evolutionary old age of the cichlid assemblage, its extreme degree of morphological differentiation, the lack of species with intermediate morphologies, and the rapidity of lineage formation have made evolutionary reconstruction difficult. The number and origin of seeding lineages, particularly the possible contribution of riverine haplochromine cichlids to endemic lacustrine lineages, remains unclear. Our phylogenetic analyses, based on mitochondrial DNA sequences of three gene segments of 49 species (25% of all described species, up to 2,400 bp each), yield robust phylogenies that provide new insights into the Lake Tanganyika adaptive radiation as well as into the origin of the Central- and East-African haplochromine faunas. Our data suggest that eight ancient African lineages may have seeded the Tanganyikan cichlid radiation. One of these seeding lineages, probably comprising substrate spawning Lamprologus -like species, diversified into six lineages that evolved mouthbrooding during the initial stage of the radiation. All analyzed haplochromines from surrounding rivers and lakes seem to have evolved within the radiating Tanganyikan lineages. Thus, our findings contradict the current hypothesis that ancestral riverine haplochromines colonized Lake Tanganyika to give rise to at least part of its spectacular endemic cichlid species assemblage. Instead, the early phases of the Tanganyikan radiation affected Central and East African rivers and lakes. The haplochromines may have evolved in the Tanganyikan basin before the lake became a hydrologically and ecologically closed system and then secondarily colonized surrounding rivers. Apparently, therefore, the current diversity of Central and East African haplochromines represents a relatively young and polyphyletic fauna that evolved from or in parallel to lineages now endemic to Lake Tanganyika.