The megadiverse haplochromine cichlid radiations of the East African lakes, famous examples of explosive speciation and adaptive radiation, are according to recent studies, introgressed by different riverine lineages. This study is informed by the first comprehensive mitochondrial and nuclear DNA dataset from extensive sampling of riverine haplochromine cichlids. It includes species from the lower Congo and Angolan (River Kwanza) drainages. Reconstruction of phylogenetic hypotheses revealed the paradox of clearly discordant phylogenetic signals. Closely related mtDNA haplotypes are distributed thousands of kilometers apart and across major African watersheds, whereas some neighbouring species carry drastically divergent mtDNA haplotypes. At shallow and deep phylogenetic layers, strong signals of hybridisation are attributed to the complex late Miocene/early Pliocene palaeo-history of African rivers. Hybridisation of multiple lineages across changing watersheds shaped each of the major haplochromine radiations in lakes Tanganyika, Victoria, Malawi and the Kalahari Palaeolakes, as well as a miniature species flock in the Congo basin (River Fwa). Based on our results, introgression occurred not only on a spatially restricted scale, but massively over almost the whole range of the haplochromine distribution. This provides an alternative view on the origin and exceptional high diversity of this enigmatic vertebrate group.