Although communicative complexity is often predicted to correlate with social complexity in animal societies, few studies have employed large-scale comparative analyses to test whether socially complex species have more complex systems of communication. I tested this social complexity hypothesis in birds (Class: Aves) using the large amount of natural history information that describes both vocal repertoire and social system in these species. To do so, I marshalled data from primary and secondary records of avian vocal repertoires (n = 253), and for each of the species in the dataset I recorded the reported repertoire size and associated species information. Using phylogenetic comparative methods, I found that cooperative breeding was a strong and repeatable predictor of vocal repertoire size, while other social variables, e.g. group size and group stability, had little or no influence on repertoire size. Importantly, repertoire sizes expanded concurrently with the evolution of cooperative breeding, suggesting a direct link between these two traits. Cooperatively breeding species devoted significantly more of their repertoire to contact calls and alarm calls. Overall, these results therefore lend support to the hypothesis that social complexity via behavioural coordination leads to increases in vocal complexity.