Initially, aposematism, which is an unprofitable trait, e.g. noxiousness conspicuously advertised to predators, appears to be a paradox since conspicuousness should increase predation by naive predators. However, reluctance of predators for eating novel prey (e.g. neophobia) might balance the initial predation caused by inexperienced predators. We tested the novelty effects on initial predation and avoidance learning in two separate conspicuousness levels of aposematic prey by using a ‘novel world’ method. Half of the wild great tits (Parus major) were trained to eat cryptic prey prior to the introduction of an aposematic prey, which potentially creates a bias against the aposematic morph. Both prey types were equally novel for control birds and they should not have shown any biased reluctance for eating an aposematic prey. Knowledge of cryptic prey reduced the expected initial mortality of the conspicuous morph to a random level whereas control birds initially ate the conspicuous morph according to the visibility risk. Birds learned to avoid conspicuous prey in both treatments but knowledge of cryptic prey did not increase the rate of avoidance learning. Predators' knowledge of cryptic prey did not reduce the predation of the less conspicuous aposematic prey and additionally predators did not learn to avoid the less conspicuous prey. These results indicate that predator psychology, which was shown as reluctance for attacking novel conspicuous prey, might have been important in the evolution of aposematism.