To understand the co-existence of rejection and acceptance of cuckoo eggs within a host population, the mechanism of egg discrimination and the cost-benefit balance of rejection behaviour were investigated. At a study site in central Japan, rejection rate of cuckoo, Cuculus canorus, eggs by great reed warblers, Acrocephalus arundinaceus, was 61·5%. An analysis of host response to natural and experimental parasitism with real cuckoo eggs, cuckoo egg models and painted host eggs indicated that: (1) hosts are more likely to reject eggs that look diVerent from their own; (2) almost all individuals (94%) can reject highly non-mimetic eggs, suggesting that there are few, if any, true accepter genotypes in the host population; (3) hosts usually reject by egg ejection; (4) during the host-laying period, the day of parasitism does not aVect host response; (5) egg types that were rejected at lower rates also took longer to be rejected; (6) acceptance was more likely to occur among mid-season breeders which consist of a higher proportion of younger females in the host population. Two experiments indicated that previous exposure of a host to its own eggs aVects its rejection behaviour, suggesting that a learning mechanism (an imprinting-like process) is involved. Parasitized nests from which the cuckoo egg was experimentally removed, or ejected by hosts, fledged more host young than nests in which the cuckoo egg was accepted. Hosts that deserted parasitized nests were likely to re-nest, and the success of re-nests was high. Costs due to breakage of host eggs occurred in only 3·5% of successful cuckoo egg ejections. A cost-benefit model of egg rejection suggests that under some circumstances, the cost of recognition errors may exceed that of parasitism. Egg variability within a clutch was higher among younger females. Some hosts rejected painted eggs and conspecific eggs based on diVerences that may occur naturally within variable clutches of other individuals. It is suggested that host egg variability is a major constraint on the learning mechanism of egg recognition. Accordingly, the cost of mistakenly rejecting an odd egg from the nest selects for greater tolerance towards divergent eggs in young breeders, and justifies a prolonged learning mechanism in which a host can learn to recognize the variation range of its own eggs. The co-existence of rejection and acceptance within the host population can therefore be explained as a compromise between the cost of parasitism and the cost of recognition errors, rather than as an evolutionary lag. This explanation is particularly pertinent where the cuckoo has evolved mimetic eggs and where the parasitism rate is low.