The haplochromine cichlids of Lake Victoria constitute a classical example of explosive speciation. Extensive intra- and interspecific variation in male nuptial coloration and female mating preferences, in the absence of postzygotic isolation between species, has inspired the hypothesis that sexual selection has been a driving force in the origin of this species flock. This hypothesis rests on the premise that the phenotypic traits that underlie behavioural reproductive isolation between sister species diverged under sexual selection within a species. We test this premise in a Lake Victoria cichlid, by using laboratory experiments and field observations. We report that a male colour trait, which has previously been shown to be important for behavioural reproductive isolation between this species and a close relative, is under directional sexual selection by female mate choice within this species. This is consistent with the hypothesis that female choice has driven the divergence in male coloration between the two species. We also find that male territoriality is vital for male reproductive success and that multiple mating by females is common.