The theory of warning signals dates back to Wallace but is still confusing, controversial and complex. Because predator avoidance of warningly coloured prey (aposematism) is based upon learning and reinforcement, it is difficult to understand how initially rare conspicuous forms subsequently become common. Here, we discuss several possible resolutions to this apparent paradox. Many of these ideas have been largely ignored as a result of implicit assumptions about predator behaviour and assumed lack of variation in the predators, prey and the predation process. Considering the spatial and temporal variation in and mechanisms of behaviour of both predators and prey will make it easier to understand the process and evolution of aposematism.