According to recent findings in wild animals, problem-solving performance on the one hand enhances reproductive success, and on the other hand can be superior in urban individuals. If urban habitats select for problem-solving skills, we expect better performance to have greater positive effect on fitness in cities than in natural habitats. We tested this idea in great tits (Parus major) at two urban sites and two rural forests by measuring problem-solving performance as latency to solve an obstacle-removal task in which the nest-box entrance was blocked. In 82% of successful pairs, the solver was the female; urban birds were more likely to solve than rural birds. Faster-solving females laid more eggs and had higher hatching success (but not nestling survival), resulting in larger brood size at fledging. These relationships were similar in both habitats, and remained qualitatively unchanged when we statistically controlled for females’ motivation (nestling-feeding activity before the task), age, trapping experience, laying date, timing of the task (time of day; age of nestlings), neophobia (latency to enter the nest box in presence of a novel object), and risk taking in the contexts of predation risk and human disturbance (latency to enter the nest box after exposure to a sparrowhawk dummy and a human, respectively). Urban females were bolder in the sparrowhawk test than rural females; they showed no difference in the neophobia and human-disturbance tests. The higher reproductive success of faster-solving females may be due to better foraging abilities allowing them to invest more into egg formation and incubation. However, this effect was similar in both habitats, implying that problem-solving skills may be similarly beneficial in cities and natural habitats. The better performance of urban birds might then be explained by lower costs of problem solving, potentially including reduced predation risk as suggested by their higher risk taking.