Brain size is an energetically costly trait to develop and maintain. Investments into other costly aspects of an organism's biology may therefore place important constraints on brain size evolution. Sexual traits are often costly and could therefore be traded off against neural investment. However, brain size may itself be under sexual selection through mate choice on cognitive ability. Here, we use guppy (Poecilia reticulata) lines selected for large and small brain size relative to body size to investigate the relationship between brain size, a large suite of male primary and secondary sexual traits, and body condition index. We found no evidence for trade-offs between brain size and sexual traits. Instead, larger-brained males had higher expression of several primary and precopulatory sexual traits – they had longer genitalia, were more colourful and developed longer tails than smaller-brained males. Larger-brained males were also in better body condition when housed in single-sex groups. There was no difference in post-copulatory sexual traits between males from the large- and small-brained lines. Our data do not support the hypothesis that investment into sexual traits is an important limiting factor to brain size evolution, but instead suggest that brain size and several sexual traits are positively genetically correlated.