Hosts may use two different strategies to ameliorate negative effects of a given parasite burden: resistance or tolerance. Although both resistance and tolerance of parasitism should evolve as a consequence of selection pressures owing to parasitism, the study of evolutionary patterns of tolerance has traditionally been neglected by animal biologists. Here, we explore geographical covariation between tolerance of magpies (Pica pica) and brood parasitism by the great spotted cuckoo (Clamator glandarius) in nine different sympatric populations. We estimated tolerance as the slope of the regression of number of magpie fledglings (i.e. host fitness) on number of cuckoo eggs laid in non-depredated nests (which broadly equals parasite burden). We also estimated prevalence of parasitism and level of host resistance (i.e. rejection rates of mimetic model eggs) in these nine populations. In accordance with the hypothetical role of tolerance in the coevolutionary process between magpies and cuckoos we found geographical variation in tolerance estimates that positively covaried with prevalence of parasitism. Levels of resistance and tolerance were not associated, possibly suggesting the lack of a trade-off between the two kinds of defences against great spotted cuckoo parasitism for magpies. We discuss the results in the framework of a mosaic of coevolutionary interactions along the geographical distribution of magpies and great spotted cuckoos for which we found evidence that tolerance plays a major role.