In many songbird species, females prefer males that sing a larger repertoire of syllables. Males with more elaborate songs have a larger high vocal centre (HVC) nucleus, the highest structure in the song production pathway. HVC size is thus a potential target of sexual selection. Here we provide evidence that the size of the HVC and other song production nuclei are heritable across individual males within a species. In contrast, we find that heritabilities of other nuclei in a song-learning pathway are lower, suggesting that variation in the sizes of these structures is more closely tied to developmental and environmental differences between individuals. We find that evolvability, a statistical measure that predicts response to selection, is higher for the HVC and its target for song production, the robustus archistriatalis (RA), than for all other brain volumes measured. This suggests that selection based on the functions of these two structures would result in rapid major shifts in their anatomy. We also show that the size of each song control nucleus is significantly correlated with the song related nuclei to which it is monosynaptically connected. Finally, we find that the volume of the telencephalon is larger in males than in females. These findings begin to join theoretical analyses of the role of female choice in the evolution of bird song to neurobiological mechanisms by which the evolutionary changes in behaviour are expressed.