Work on the Lake Victoria cichlids Pundamilia nyererei (red dorsum males, deeper water), Pundamilia pundamilia (blue males, shallower water) and related species pairs has provided insights into processes of speciation. Here, we investigate the female mating behaviour of 5 Pundamilia species and 4 of their F1 hybrids through mate choice trials and paternity testing. Complete assortative mating was observed among all sympatric species. Parapatric species with similar depth habitat distributions interbred whereas other parapatric and allopatric species showed complete assortative mating. F1 hybrids mated exclusively with species accepted by females of the parental species. The existence of complete assortative mating among some currently allopatric species suggests that pre-existing mating barriers could be sufficient to explain current patterns of co-existence, although, of course, many other factors may be involved. Regardless of the mechanism, mating preferences may influence species distribution in potentially hybridizing taxa, such as in the adaptive radiation of cichlid fish. We suggest that this at least partly explains why some species fail to establish breeding populations in locations where they are occasionally recorded. Our results support the notion that the mating preferences of potentially cross-breeding species ought to be included in coexistence theory.