A long history of research focused on the East Africa cichlid radiations (EAR) revealed discrepancies between mtDNA and nuclear phylogenies, suggesting that interspecific hybridisation may have been significant during the radiation of these fishes. The approximately 250 cichlid species of Lake Tanganyika have their roots in a monophyletic African cichlid assemblage, but controversies remain about the precise phylogenetic origin and placement of different lineages and consequently about L. Tanganyika colonization scenarios. 3312 AFLP loci and the mitochondrial ND2 gene were genotyped for 91 species representing almost all major lacustrine and riverine haplotilapiine east African cichlid lineages with a focus on L. Tanganyika endemics. Explicitly testing for the possibility of ancient hybridisation events, a comprehensive phylogenetic network hypothesis is proposed for the origin and diversification of L. Tanganyika cichlids. Inference of discordant phylogenetic signal strongly suggests that the genomes of two endemic L. Tanganyika tribes, Eretmodini and Tropheini, are composed of an ancient mixture of riverine and lacustrine lineages. For the first time a strong monophyly signal of all non-haplochromine mouthbrooding species endemic to L. Tanganyika (“ancient mouthbrooders”) was detected. Further, in the genomes of early diverging L. Tanganyika endemics Trematocarini, Bathybatini, Hemibatini and Boulengerochromis genetic components of other lineages belonging to the East African Radiation appear to be present. In combination with recent palaeo-geological results showing that tectonic activity in the L. Tanganyika region resulted in highly dynamic and heterogeneous landscape evolution over the Neogene and Pleistocene, the novel phylogenetic data render a single lacustrine basin as the geographical cradle of the endemic L. Tanganyika cichlid lineages unlikely. Instead a scenario of a pre-rift origin of several independent L. Tanganyika precursor lineages which diversified in ancient rivers and precursor lakes and then amalgamated in the extant L. Tanganyika basin is put forward as an alternative: the 'melting pot Tanganyika' hypothesis.