Prevailing theory assumes cuckoos lay at random among host nests within a population, although it has been suggested that cuckoos could choose large nests and relatively active pairs within host populations. We tested the hypothesis that egg matching could be improved by cuckoos choosing nests in which host eggs more closely match their own, by assessing matching and monitoring nest fate in great reed warblers naturally or experimentally parasitized by eggs of European cuckoos. A positive correlation between cuckoo and host egg visual features suggests that cuckoos do not lay at random within a population, but choose nests and this improves egg matching: naturally parasitized cuckoo eggs were more similar to host eggs as perceived by humans and as measured by spectrophotometry. Our results suggest a hitherto overlooked step in cuckoo-host evolutionary arms races, and have nontrivial implications for the common experimental practice of artificially parasitizing clutches.