Lake Tanganyika comprises a cichlid species flock with substrate-breeding and mouthbrooding lineages. While sexual selection via mate choice on male mating color is thought to boost speciation rates in mouthbrooding cichlids, this is not the case in substrate-breeding lamprologines, which mostly form stable pairs and lack sexual dichromatism. We present a comprehensive reconstruction of the evolution of the cichlid tribe Lamprologini, based upon mtDNA sequences and multilocus nuclear DNA (AFLP) markers. Twelve mtDNA clades were identified, seven of which were corroborated by the AFLP tree. The radiation is likely to have started about 5.3 MYA, contemporarily with that of the mouthbrooding C-lineage, and probably triggered by the onset of deep-water conditions in Lake Tanganyika. Neither the Congo- nor the Malagarazi River species form the most ancestral branch. Several conflicts in the mtDNA phylogeny with taxonomic assignments based upon color, eco-morphology and behavior could be resolved and complemented by the AFLP analysis. Introgressive hybridization upon secondary contact seems to be the most likely cause for paraphyly of taxa due to mtDNA capture in species involving brood-care helpers, while accidental hybridization best explains the para- or polyphyly of several gastropod shell breeders. Taxonomic error or paraphyly due to the survival of ancestral lineages appear responsible for inconsistencies in the genera Lamprologus and Neolamprologus.