The evolution of adaptive mate choice and sexual selection for traits indicating the genetic quality of prospective mates depends upon processes maintaining heritable variation for these traits. A new mechanism for the maintenance of `good genes' is proposed: in migratory birds, variation in the genes influencing migration is maintained in the population by fluctuating directional selection caused by the effects of climatic trends on the suitability of overwintering environments. The suitability of a surviving migrant's overwintering area affects its spring condition and is reflected in its breeding plumage; environmentally influenced phenotypic condition is thereby associated with migratory genes and condition-dependent traits available for sexual selection. This hypothesis predicts that migratory birds should be more colourful than residents, whereas, because in migrants the correlation and hence coevolution between parasitism and coloration is lower than in residents, the Hamilton-Zuk hypothesis of parasite resistance `good genes' predicts the opposite. Comparison of 37 phylogenetically independent intrageneric pairs of species showed migrants to have significantly more contrasting and colourful plumage and bare parts than residents: the `good migrations' mechanism rather than the Hamilton-Zuk hypothesis is thus supported for migrant bird coloration.