The question, “Why should prey advertise their presence to predators using warning coloration?” has been asked for over 150 years. It is now widely acknowledged that defended prey use conspicuous or distinctive colors to advertise their toxicity to would-be predators: a defensive strategy known as aposematism. One of the main approaches to understanding the ecology and evolution of aposematism and mimicry (where species share the same color pattern) has been to study how naive predators learn to associate prey’s visual signals with the noxious effects of their toxins. However, learning to associate a warning signal with a defense is only one aspect of what predators need to do to enable them to make adaptive foraging decisions when faced with aposematic prey and their mimics. The aim of our review is to promote the view that predators do not simply learn to avoid aposematic prey, but rather make adaptive decisions about both when to gather information about defended prey and when to include them in their diets. In doing so, we reveal what surprisingly little we know about what predators learn about aposematic prey and how they use that information when foraging. We highlight how a better understanding of predator cognition could advance theoretical and empirical work in the field.