In animals, individual differences in learning ability are common and are in part explained by genetic differences, developmental conditions and by general experience. Yet, not all variations in learning are well understood. Individual differences in learning may be associated with elementary individual characteristics that are consistent across situations and over time, commonly referred to as personality or temperament. Here, we tested whether or not male great tits (Parus major) from two selection lines for fast or slow exploratory behaviour, an operational measure for avian personality, vary in their learning performance in two related consecutive tasks. In the first task, birds had to associate a colour with a reward whereas in the second task, they had to associate a new colour with a reward ignoring the previously rewarded colour. Slow explorers had shorter latencies to approach the experimental device compared with fast explorers in both tasks, but birds from the two selection lines did not differ in accomplishing the first task, that is, to associate a colour with a reward. However, in the second task, fast explorers had longer latencies to solve the trials than slow explorers. Moreover, relative to the number of trials needed to reach the learning criteria in the first task, birds from the slow selection line took more trials to associate a new colour with a reward while ignoring the previously learned association compared with birds from the fast selection line. Overall, the experiments suggest that personality in great tits is not strongly related to learning per se in such an association task, but that birds from different selection lines might express different learning strategies as birds from the different selection lines were differently affected by their previous learning performance.