Although parasites and their hosts often coexist in a set of environmentally differentiated populations connected by gene flow, few empirical studies have considered a role of environmental variation in shaping correlations between traits of hosts and parasites. Here, we studied for the first time the association between the frequency of adaptive parasitic common cuckoo Cuculus canorus phenotypes in terms of egg matching and level of defences exhibited by its reed warbler Acrocephalus scirpaceus hosts across seven geographically distant populations in Europe. We also explored the influence of spring climatic conditions experienced by cuckoos and hosts on cuckoo-host egg matching. We found that between-population differences in host defences against cuckoos (i.e. rejection rate) covaried with between-population differences in degree of matching. Between-population differences in host egg phenotype were associated with between-population differences in parasitism rate and spring climatic conditions, but not with host level of defences. Between-population differences in cuckoo egg phenotype covaried with between-population differences in host defences and spring climatic conditions. However, differences in host defences still explained differences in mimicry once differences in climatic conditions were controlled, suggesting that selection exerted by host defences must be strong relative to selection imposed by climatic factors on egg phenotypes.