Females often choose their mates, instead of mating at random, even when a father contributes nothing but genes to his offspring. Costly female preferences for males with exaggerated traits that reduce viability, such as the peacock's tail, are particularly puzzling. Such preferences can evolve if directly favoured by natural selection or when the exaggerated trait, although maladaptive per se, indicates high overall quality of the male's genotype. Two recent analyses suggested that the advantage to mate choice based on genetic quality is too weak to explain extreme cases of exaggeration of display traits and the corresponding preferences. We studied coevolution of a female mate-preference function and a genotype-dependent male display function where mutation supplies variation in genotype quality and mate preference is costly. Preference readily evolves, often causing extreme exaggeration of the display. Mate choice and trait expression can approach an equilibrium, or a limit cycle, or exaggeration can proceed forever, eventually causing extinction.