To avoid potentially noxious prey, predators need to discriminate between palatable and unpalatable prey species. Unpalatable prey often exhibits visual warning signals, which can consist of multiple components, such as color and pattern. Although the role of particular components of visual warning signals in predator discrimination learning has been intensively studied, the importance of different components for predator memory is considerably less understood. In this study, we tested adult wild-caught great tits (Parus major) to find out which components of prey visual warning signals are important when the birds learn to discriminate between palatable and unpalatable prey, and when they remember their experience over a longer time period. Birds were trained to discriminate between palatable and unpalatable artificial prey items that differed in both color and pattern. After four weeks, the birds were retested in three groups: the first group was presented with the same prey as in the training, the second group was tested with the two prey types differing only in color, and the third group could use only the pattern as a discrimination trait. The results suggest that the birds remember their experience with unpalatable prey even after the period of four weeks. Although the color appears to be more important than the pattern, the combination of both signal components is more effective for prey recognition after several weeks than either the color or pattern alone.