<p>In recent years, avian cognition has become a subject of intensive research. Most studies have, nevertheless, only focused on a few bird taxa known for their high cognitive capacities and comparative studies of other species are scarce. Testing problem-solving abilities of birds can give us an insight into how they can adapt to changing environments through innovation. Lever-pulling is a well-known paradigm to investigate problem-solving in various species, and analysing subjects’ behaviour leading to solving the task could give us important insights into the cognitive mechanisms and motor propensities potentially affecting success. Although blue tits (<i>Cyanistes caeruleus</i>) and great tits (<i>Parus major</i>) are known for successful performance during various cognitive tasks, other small passerine species inhabiting similar environments remain understudied. In contrast to great tits and blue tits, coal tits (<i>Periparus ater</i>) and nuthatches (<i>Sitta europaea</i>) are food-storing species, thus interspecific comparisons could reveal whether different foraging strategies are linked to problem-solving performance. We tested wild-caught blue and great tit adults and hand-reared juveniles of all four species in a food-motivated lever-pulling task. Results indicate species-specific differences among juveniles, with coal tits and nuthatches demonstrating greater success. Birds from both age categories performed similarly, but juveniles were faster to solve the task than adults. Success was positively influenced by individual traits such as persistence, accuracy and motivation from prior experience, but not by the initial latency to approach the apparatus. Our results reveal how both foraging strategy and individual traits could be related to innovative problem-solving in small passerines.</p>