Although, generally, the origin of sex-limited traits remains elusive, the sensory exploitation hypothesis provides an explanation for the evolution of male sexual signals. Anal fin egg-spots are such a male sexual signal and a key characteristic of the most species-rich group of cichlid fishes, the haplochromines. Males of about 1500 mouth-brooding species utilize these conspicuous egg-dummies during courtship--apparently to attract females and to maximize fertilization success. Here we test the hypothesis that the evolution of haplochromine egg-spots was triggered by a pre-existing bias for eggs or egg-like coloration. To this end, we performed mate-choice experiments in the basal haplochromine Pseudocrenilabrus multicolor, which manifests the plesiomorphic character-state of an egg-spot-less anal fin. Experiments using computer-animated photographs of males indeed revealed that females prefer images of males with virtual ('in-silico') egg-spots over images showing unaltered males. In addition, we tested for color preferences (outside a mating context) in a phylogenetically representative set of East African cichlids. We uncovered a strong preference for yellow, orange or reddish spots in all haplochromines tested and, importantly, also in most other species representing more basal lines. This pre-existing female sensory bias points towards high-quality (carotenoids-enriched) food suggesting that it is adaptive.