Visual complexity is ubiquitous in nature. Drivers of complexity include selection in coevolutionary arms races between antagonists. However, the causes and consequences of biological complexity and its perception are largely understudied, partly because complexity is difficult to quantify. Here, we address this by studying egg pattern complexity and its perception in hosts (tawny-flanked prinia Prinia subflava), which visually recognize and reject mimetic eggs of their virulent brood parasite (cuckoo finch Anomalospiza imberbis). Using field data and an optimization algorithm, we compute a complexity metric which predicts rejection of experimentally placed conspecific eggs in prinia nests. Real cuckoo finch eggs exhibit significantly lower pattern complexity than prinia eggs, suggesting that high complexity benefits hosts because it distinguishes host eggs from parasitic eggs. We show that prinias perceive complexity differences according to Weber's law of proportional processing (i.e. relative, rather than absolute, differences between stimuli are processed in discrimination, such that two eggs with simple patterns are more easily discriminable than two with complex patterns). This may influence coevolutionary trajectories of hosts and parasites. The new methods presented for quantifying complexity and its perception can help us to understand selection pressures driving the evolution of complexity and its consequences for species interactions.