Individuals develop innovative behaviours to solve foraging challenges in the face of changing environmental conditions. Little is known about how individuals differ in their tendency to solve problems and in their subsequent use of this solving behaviour in social contexts. Here we investigated whether individual variation in problem-solving performance could be explained by differences in the likelihood of solving the task, or if they reflect differences in foraging strategy. We tested this by studying the use of a novel foraging skill in groups of great tits (Parus major), consisting of three naive individuals with different personality, and one knowledgeable tutor. We presented them with multiple, identical foraging devices over eight trials. Though birds of different personality type did not differ in solving latency; fast and slow explorers showed a steeper increase over time in their solving rate, compared to intermediate explorers. Despite equal solving potential, personality influenced the subsequent use of the skill, as well as the pay-off received from solving. Thus, variation in the tendency to solve the task reflected differences in foraging strategy among individuals linked to their personality. These results emphasize the importance of considering the social context to fully understand the implications of learning novel skills.