Complex vocal learning, a critical component of human spoken language, has been assumed to be associated with more-advanced cognitive abilities. Tests of this hypothesis between individuals within a species have been inconclusive and have not been done across species. In this work, we measured an array of cognitive skills-namely, problem-solving, associative and reversal learning, and self-control-across 214 individuals of 23 bird species, including 19 wild-caught songbird species, two domesticated songbird species, and two wild-caught vocal nonlearning species. We found that the greater the vocal learning abilities of a species, the better their problem-solving skills and the relatively larger their brains. These conclusions held when controlling for noncognitive variables and phylogeny. Our results support a hypothesis of shared genetic and cognitive mechanisms between vocal learning, problem-solving, and bigger brains in songbirds.