Avian brood parasites reduce the reproductive output of their hosts and thereby select for defence mechanisms such as ejection of parasitic eggs. Such defence mechanisms simultaneously select for counter-defences in brood parasites, causing a coevolutionary arms race. Although coevolutionary models assume that defences and counter-defences are genetically influenced, this has never been demonstrated for brood parasites. Here, we give strong evidence for genetic differences between ejector and nonejectors, which could allow the study of such host defence at the genetic level, as well as studies of maintenance of genetic variation in defences. Briefly, we found that magpies, that are the main host of the great spotted cuckoo in Europe, have alleles of one microsatellite locus (Ase64) that segregate between accepters and rejecters of experimental parasitic eggs. Furthermore, differences in ejection rate among host populations exploited by the brood parasite covaried significantly with the genetic distance for this locus.