One of the best known outcomes of coevolution between species is the rejection of mimetic parasite eggs by avian hosts, which has evolved to reduce costly cuckoo parasitism. How this behavioral adaptation varies along the life of individual hosts remains poorly understood. Here we identify for the first time, lifetime patterns of egg rejection in a parasitized long-lived bird, the magpie Pica pica and show that, during the years they were studied, some females accept, others reject, and some others modify their response to model eggs, in all cases switching from acceptance to rejection. Females tested in their first breeding attempt always accepted the model egg, even those individuals whose mothers were egg rejecters. A longitudinal analysis showed that the probability of egg rejection increased with the relative age of the female, but was not related to the risk of parasitism in the population. We conclude that ontogeny plays a fundamental role in the process leading to egg rejection in magpies.