Males of many species have complex behavioral sexual displays and it is possible that these displays indicate aspects about male quality because of their relationship with cognitive ability. However, the relationship between behavioral display traits, cognitive ability, and reproductive success has received little attention. Satin bowerbirds, Ptilonorhynchus violaceus, are an excellent species for studying this relationship because their complex male courtship suggests a selective advantage to individuals with superior cognitive abilities. Here I show that cognitive performance can have important effects on mating success and the quality of behavioral displays. First, I present males with two novel problem solving tests and find that males who are better at solving these problems have higher mating success, establishing a link between male cognitive ability and sexual attractiveness. Second, I add four additional cognitive tests to expand the diversity of cognitive abilities tested and construct two measures of general cognitive ability using these data: the scores from an analysis that best explains covariation among performance on the different cognitive tests (g), and the average rank score on these cognitive tests (“IQ"). I show that these measures of general cognitive ability, as well as the majority of the independent cognitive tests, are positively associated with mating success. Third, I construct a different composite measure of male cognitive ability using an analysis that determines the combination of cognitive traits that make males most successful in attracting females (f). I show that this measure is significantly associated with my measures of general cognitive ability, suggesting that evolution of cognitive ability in bowerbirds is possible if there is sufficient heritability. I construct three different aggregate measures of male display quality (produced from four behavioral display traits) and find that they are all associated with f and with mating success. Finally, I show some support for the hypothesis that separate display traits may indicate different aspects of male cognitive ability. These results suggest that behavioral display traits may have a special role in sexual selection because of their connection to cognitive ability. Overall, this research highlights the importance of considering the interrelationship between cognitive ability and sexual selection.