Adapting to environmental change is a major challenge faced by animals and the role of individual behavioural differences in facilitating this process is currently the focus of much research. Innovation, the generation of a novel behaviour or use of a known behaviour in a novel context, is one form of behaviour that enables animals to respond to change. By deciphering the mechanisms underlying innovativeness, especially those that explain consistent differences between individuals, we can further understand the consequences of this behavioural variation. We tested whether motivation, experience, inhibitory control and personality were linked to different stages of sequential innovative problem-solving performance among great tits, Parus major, and of their overall innovativeness across tasks. We gave animals originating from lines bidirectionally selected for fast or slow early exploratory behaviour, a multiaccess problem-solving device. Diverse motor skills and behavioural flexibility were required to solve all three different access points sequentially over trials. Food-deprived, highly motivated birds had shorter latency to touch the device, were more likely to solve an access point within a trial, and solved a greater diversity of them, than their less motivated counterparts. Solving success increased with accuracy when interacting with the device (proportion of touches to functional components of the device compared to all touches to the device per trial), and with previous experience. Personality selection lines and inhibitory control had little effect. Repeatability analysis showed that between-individual differences in problem-solving performance were explained by: (1) pseudorepeatable effects (upward bias) linked to hunger-induced motivation, (2) repeatable differences in accuracy when interacting with devices, and (3) a feedback loop caused by experience gained over successive trials. Our results highlight the challenges of characterizing consistent individual differences in behaviour generally and support the idea that complex sources of variation play an important role in problem-solving performance.