Many phenotypic traits such as behaviour, body shape, and colour are shaped by a combination of both natural and sexual selection. However, the two evolutionary processes often act in opposition. Natural selection usually acts to improve fitness by increasing survival. In contrast, sexual selection acts to improve fitness by increasing the likelihood of successful mating. This often results in characters, such as conspicuous ornaments and breeding colours, that seem to reduce survival. The interaction between these two modes of selection has been well studied for many traits, but the relative effects of natural and sexual selection on brain evolution is still relatively unknown. How does each type of selection influence brain structure? And how do the relative roles of natural and sexual selection compare to those on other traits closely associated with fitness such as colouration, body size, and key life history traits? To test the interaction between natural and sexual selection, we used high-resolution magnetic resonance imaging combined with traditional histology to document brain structure in 14 lizard species belonging to the Australian genus Ctenophorus (known as dragons). These species exist in discrete ecological types or “ecotypes”, which are behaviourally distinct, and vary in the strength of sexual selection they experience, which also influences their behaviour.  At the level of major brain regions we found only evidence of natural selection acting on brain structure. However, when examining specific brain nuclei that are directly involved with reproductive behaviours we also found evidence that sexual selection has shaped the structure of the brain. We show that both natural and sexual selection have affected the evolution of brain structure.