Avian brood parasites should target the most profitable host species, but current conditions might locally influence their choice, producing geographic mosaics of coevolution. Throughout Europe, the magpie Pica pica has been invariably reported as the primary host of the great spotted cuckoo Clamator glandarius, whereas the carrion crow Corvus corone is the secondary one. However, we found that this pattern reversed in northern Spain, where up to 70% of carrion crow nests were parasitized versus 20% of magpie nests. In southern Spain, conversely, parasitism increased proportionally in both hosts (up to approximately 90% of available nests) throughout the 3 years of study. Surprisingly, magpies provided the best reproductive output for cuckoos in both areas, in contrast with cuckoo’s preference for the crow host in the north. Genetic data ruled out the presence of different host-specific races in this brood parasite, dismissing the hypothesis that a prevalence of different gentes at the 2 sites explained the observed variability in host choice. Instead, we found that magpie nests in the south were easier to reach and more scattered than in the north, where cuckoos preferentially targeted nests that were less concealed and more isolated. We suggest that the habitat constraints parasitism on magpies in the north, driving cuckoo host choice toward the crows. The coevolutionary scenario therefore includes a 3-way interaction, where the pressure that the parasite puts on a host species in a given place critically depends on the environmentally mediated interaction between the same parasite and a different host.