Parasites require synchrony with their hosts so if host timing changes with climate change, some parasites may decline and eventually go extinct. Residents and short-distance migrant hosts of the brood parasitic common cuckoo, Cuculus canorus , have advanced their phenology in response to climate change more than long-distance migrants, including the cuckoo itself. Because different parts of Europe show different degrees of climate change, we predicted that use of residents or short-distance migrants as hosts should have declined in areas with greater increase in spring temperature. Comparing relative frequency of parasitism of the two host categories in 23 European countries before and after 1990, when spring temperatures in many areas had started to increase, we found that relative parasitism of residents and short-distance migrants decreased. This change in host use was positively related to increase in spring temperature, consistent with the prediction that relative change in phenology for different migrant classes drives host-use patterns. These findings are consistent with the hypothesis that climate change affects the relative abundance of different host races of the common cuckoo.