Aposematic species, which signal conspicuously of their unprofitability to predators, have puzzled evolutionary biologists for over a century(.1,2). Although conspicuousness of unpalatable prey improves avoidance learning by predators(3-5), it also involves an evolutionary paradox: with increasing detectability(4,6-8) the deviant aposematic prey would suffer high predation initially from naive predators. Here we test a neglected idea(7-11) that aposematic coloration may evolve by gradual change rather than by major mutations. Weak signals did not suffer high initial predation, but predators (great tits, Parus major) did not learn to separate them from cryptic palatable prey. Furthermore, enhanced avoidance of more conspicuous signals occurred only if predators had previously encountered relatively strong signals. Thus, the gradual-change hypothesis does not provide an easy solution to the initial evolution of aposematism through predator learning. However, the possibility remains that cost-free step-wise mutations over the range of weak signals could accumulate under neutral selection to produce effective strong signals.