Hybridization among littoral cichlid species in Lake Tanganyika was inferred in several molecular phylogenetic studies. The phenomenon is generally attributed to the lake level-induced shoreline and habitat changes. These allow for allopatric divergence of geographically fragmented populations alternating with locally restricted secondary contact and introgression between incompletely isolated taxa. In contrast, the deepwater habitat is characterized by weak geographic structure and a high potential for gene flow, which may explain the lower species richness of deepwater than littoral lineages. For the same reason, divergent deepwater lineages should have evolved strong intrinsic reproductive isolation already in the incipient stages of diversification, and, consequently, hybridization among established lineages should have been less frequent than in littoral lineages. We test this hypothesis in the endemic Lake Tanganyika deepwater cichlid tribe Bathybatini by comparing phylogenetic trees of Hemibates and Bathybates species obtained with nuclear multilocus AFLP data with a phylogeny based on mitochondrial sequences. Consistent with our hypothesis, largely congruent tree topologies and negative tests for introgression provided no evidence for introgressive hybridization between the deepwater taxa. Together, the nuclear and mitochondrial data established a well-supported phylogeny and suggested ecological segregation during speciation.