Common cuckoos (Cuculus canorus) are obligate brood parasites, laying eggs into nests of small songbirds. The cuckoo hatchling evicts all eggs and young from a nest, eliminating hosts' breeding success. Despite the consistently high costs of parasitism by common cuckoos, great reed warbler (Acrocephalus arundinaceus) hosts sometime accept and other times reject parasitic eggs. To explore the cognitive basis of this seemingly maladaptive variation in host responses, we documented differences in egg rejection rates within 1-day periods just before and during the egg-laying cycle across host nests. Hosts rejected cuckoo eggs at 28% of nests during the pre-egg-laying stage, but when cuckoos exchanged the first host egg with the parasite egg, rejections increased to 75%. Even later, when several host eggs remained in a nest after parasitism, rejection rate fell to 37.5%. Experimental parasitism with conspecific eggs on the first and second day of host laying showed a similar directional change in relative rejection rates, dropping from 35 to 0%. Mistakes in egg discrimination (ejection error and ejection cost) were observed mostly in the latter part of the laying cycle, mainly when nests contained 5-6 eggs. These correlational and experimental patterns of egg rejection support a cognitive process of egg discrimination through several shifts in hosts' optimal acceptance thresholds of foreign eggs. The results are also consistent with the evolution of foreign egg rejection in the context of nest-sanitation (i.e. the removal of foreign objects). Our results suggest that common cuckoo hosts may recognize more eggs than they reject. This implies that the experience of the host with one or more of its own eggs in the clutch is a key factor in rejecting parasite eggs by allowing inspection and learning about their own clutch.