Among the huge radiations of haplochromine cichlid fish in Lakes Malawi and Victoria, closely related species are often reproductively isolated via female mate choice although viable fertile hybrids can be produced when females are confined only with heterospecific males. We generated F(2) hybrid males from a cross between a pair of closely related sympatric cichlid fish from Lake Malawi. Laboratory mate choice experiments using microsatellite paternity analysis demonstrated that F(2) hybrid males differed significantly in their attractiveness to females of the two parental species, indicating heritable variation in traits involved in mate choice that may contribute to reproductive isolation between these species. We found no significant correlation between male mating success and any measurement of male colour pattern. A simple quantitative genetic model of reproductive isolation suggests that there may be as few as two chromosomal regions controlling species-specific attractiveness. We propose that adaptive radiation of Lake Malawi cichlids could be facilitated by the presence of genes with major effects on mate choice and reproductive isolation.