Phenological responses to climate change vary among taxa and across trophic levels. This can lead to a mismatch between the life cycles of ecologically interrelated populations (e.g. predators and prey), with negative consequences for population dynamics of some of the interacting species. Here we provide, to our knowledge, the first evidence that climate change might disrupt the association between the life cycles of the common cuckoo ( Cuculus canorus ), a migratory brood parasitic bird, and its hosts. We investigated changes in timing of spring arrival of the cuckoo and its hosts throughout Europe over six decades, and found that short-distance, but not long-distance, migratory hosts have advanced their arrival more than the cuckoo. Hence, cuckoos may keep track of phenological changes of long-distance, but not short-distance migrant hosts, with potential consequences for breeding of both cuckoo and hosts. The mismatch to some of the important hosts may contribute to the decline of cuckoo populations and explain some of the observed local changes in parasitism rates of migratory hosts.