Accurate recognition of salient cues is critical for adaptive responses, but the underlying sensory and cognitive processes are often poorly understood. For example, hosts of avian brood parasites have long been assumed to reject foreign eggs from their nests based on the total degree of dissimilarity in colour to their own eggs, regardless of the foreign eggs' colours. We tested hosts' responses to gradients of natural (blue-green to brown) and artificial (green to purple) egg colours, and demonstrate that hosts base rejection decisions on both the direction and degree of colour dissimilarity along the natural, but not artificial, gradient of egg colours. Hosts rejected brown eggs and accepted blue-green eggs along the natural egg colour gradient, irrespective of the total perceived dissimilarity from their own egg's colour. By contrast, their responses did not vary along the artificial colour gradient. Our results demonstrate that egg recognition is specifically tuned to the natural gradient of avian eggshell colour and suggest a novel decision rule. These results highlight the importance of considering sensory reception and decision rules when studying perception, and illustrate that our understanding of recognition processes benefits from examining natural variation in phenotypes.