Natural selection may favour sexually similar brain size owing to similar selection pressures in males and females, while sexual selection may lead to sexually dimorphic brains. For example, sperm competition involves clear–cut sex differences in behaviour, as males display, mate guard and copulate with females, while females choose among males, and solicit or reject copulations. These behaviours may require fundamentally different neural government in the two sexes leading to sex–dependent brain evolution. Using two phylogenetic approaches in a comparative study, we tested for roles of both natural and sexual–selection pressures on brain size evolution of birds. In accordance with the natural–selection theory, relative brain size of males coevolved with that of females, which may be the result of adaptation to similar environmental constraints such as feeding innovation. However, the mode of brain size evolution differed between the sexes, and factors associated with sperm competition as reflected by extra–pair paternity may give rise to sexually size dimorphic brains. Specifically, species in which females have larger brains than males were found to have a higher degree of extra–pair paternity independently of potentially confounding factors, whereas species in which males have relatively larger brains than females appeared to have lower rates of extra–pair paternity. Hence, the evolution of sperm competition may select for complex behaviours together with the associated neural substrates in the sex that has a higher potential to control extra–pair copulations at the observed levels. Brain function may thus be affected differently in males and females by sexual selection.