Song and brain structure are compared amongst 41 species of oscine birds by using the method of independent evolutionary contrasts. We find a significant correlation between the relative volume of the song control centre, the high vocal centre (HVC), and the number of song types typically found in the repertoire. Relative HVC volume is not correlated with the number of different syllable types per song bout. The relative volume of a second song nucleus, area X, is not significantly correlated with either measure. Relative HVC volume is uncorrelated with relative volume of the hippocampus, a brain area involved in other forms of memory. This is the first evidence for repeated independent evolution of an association between complexity of learned song and the relative volume of one of the song control nuclei thought to be involved in song learning.