Matching the timing of spring arrival to the breeding grounds with hosts and prey is crucial for migratory brood parasites such as cuckoos. Previous studies have focused mostly on phenological mismatch between a single cuckoo species and its hosts but information regarding climate-driven mismatch between multiple sympatric cuckoo species and their hosts and invertebrate prey is still lacking. Here, we analysed long-term data (1988–2023) on the first arrival date of two declining migratory cuckoo species and their 14 migratory host species breeding in sympatry and prey emergence date in Tatarstan (southeast Russia). We found that the common cuckoo ( Cuculus canorus ; wintering in Africa) generally arrived on breeding grounds earlier than the oriental cuckoo ( Cuculus optatus ; wintering in southeast Asia and Australia). Both cuckoos have advanced their arrival dates over 36 years but less than their hosts, potentially resulting in an increasing arrival mismatch between cuckoos and their hosts. Moreover, cuckoo arrival advanced less than the emergence date of their prey over time. These observations indicate that climate change may disrupt co-fluctuation in the phenology of important life stages between multiple sympatric brood parasites, their hosts and prey with potential cascading consequences for population dynamics of involved species.