Arms races between avian brood parasites and their hosts often result in parasitic mimicry of host eggs, to evade rejection. Once egg mimicry has evolved, host defences could escalate in two ways: (i) hosts could improve their level of egg discrimination; and (ii) negative frequency-dependent selection could generate increased variation in egg appearance (polymorphism) among individuals. Proficiency in one defence might reduce selection on the other, while a combination of the two should enable successful rejection of parasitic eggs. We compared three highly variable host species of the Afrotropical cuckoo finch Anomalospiza imberbis , using egg rejection experiments and modelling of avian colour and pattern vision. We show that each differed in their level of polymorphism, in the visual cues they used to reject foreign eggs, and in their degree of discrimination. The most polymorphic host had the crudest discrimination, whereas the least polymorphic was most discriminating. The third species, not currently parasitized, was intermediate for both defences. A model simulating parasitic laying and host rejection behaviour based on the field experiments showed that the two host strategies result in approximately the same fitness advantage to hosts. Thus, neither strategy is superior, but rather they reflect alternative potential evolutionary trajectories.