Inter– and intraspecific variations in the sizes of specific avian brain regions correspond to the complexity of the behaviour that they govern. However, no study has demonstrated a relationship between gross brain size and behavioural complexity, a hypothesis that has been proposed to explain the unusually large human brain. I show, using X–rays of museum specimens, that species of bowerbirds that build bowers have relatively larger brains than both related and ecologically similar but unrelated species that do not build bowers. Bower design varies across species from simple cleared courts to ornate, hut–like structures large enough to contain a small child. Furthermore, species building more complex bowers have relatively larger brains, both within each of the two different bower–building clades and across the family as a whole, controlling for phylogeny. Such gross differences in brain size are surprising and may reflect the range of cognitive processes necessary for successful bower building. The relationships are strongest for males, the bower–building sex, although there is a similar trend in females. Because the size and complexity of bower design is targeted by female choice, the observation that relative brain size is related to bower complexity suggests that sexual selection may drive gross brain enlargement.