Cognition has been studied intensively for several decades, but the evolutionary processes that shape individual variation in cognitive traits remain elusive [1-3]. For instance, the strength of selection on a cognitive trait has never been estimated in a natural population, and the possibility that positive links with life history variation [1-5] are mitigated by costs [6] or confounded by ecological factors remains unexplored in the wild. We assessed novel problem-solving performance in 468 wild great tits Parus major temporarily taken into captivity and subsequently followed up their reproductive performance in the wild. Problem-solver females produced larger clutches than non-solvers. This benefit did not arise because solvers timed their breeding better, occupied better habitats, or compromised offspring quality or their own survival. Instead, foraging range size and day length were relatively small and short, respectively, for solvers, suggesting that they were more efficient at exploiting their environment. In contrast to the positive effect on clutch size, problem solvers deserted their nests more often, leading to little or no overall selection on problem-solving performance. Our results are consistent with the idea that variation in cognitive ability is shaped by contrasting effects on different life history traits directly linked to fitness [1,3].