Adaptation to urban habitat requires modifications in various combinations of cognitive and behavioral traits enabling individuals to exploit urban resources. It is hypothesized that personality traits and cognitive skills such as problem-solving and learning should vary following urbanization. However, evolving and maintaining particular cognitive abilities could involve costs, either through physiological constraints or through differential exposure to pathogens. For instance, cognition could be traded-off against other energetically costly traits such as immunity. To test this hypothesis, we assessed problem solving abilities, personality, parasite load and immunocompetence of wild-caught Barbados bullfinches, a particularly opportunistic and behaviorally innovative bird species, in a broad range of differently urbanized habitats. Birds from urbanized areas were better at problem solving than their rural counterparts, in two different problem solving tasks. They were also less shy and, surprisingly, more neophobic than rural birds. Urban birds also had a better immunocompetence, which was measured using PHA antigen. Nonetheless, parasite prevalence was lower in urban compared to rural environments, suggesting that the higher immunocompetence is not simply due to a higher exposure to parasites. Therefore, cognition and immunocompetence do not seem to be traded-off against each other so that birds living in urban environments have better problem solving abilities but also a better immunity. Our results suggest that urbanization selects for particular combinations of behavioral and physiological traits that presumably confer advantages in this particular environment. This study sheds light on the constraints acting on birds that are subject to changing environments, particularly in the context of urbanization.