Sexual selection is responsible for the evolution of male ornaments and armaments, but its role in the evolution of cognition--the ability to process, retain and use information--is largely unexplored. Because successful courtship is likely to involve processing information in complex, competitive sexual environments, we hypothesized that sexual selection contributes to the evolution and maintenance of cognitive abilities in males. To test this, we removed mate choice and mate competition from experimental populations of Drosophila melanogaster by enforcing monogamy for over 100 generations. Males evolved under monogamy became less proficient than polygamous control males at relatively complex cognitive tasks. When faced with one receptive and several unreceptive females, polygamous males quickly focused on receptive females, whereas monogamous males continued to direct substantial courtship effort towards unreceptive females. As a result, monogamous males were less successful in this complex setting, despite being as quick to mate as their polygamous counterparts with only one receptive female. This diminished ability to use past information was not limited to the courtship context: monogamous males (but not females) also showed reduced aversive olfactory learning ability. Our results provide direct experimental evidence that the intensity of sexual selection is an important factor in the evolution of male cognitive ability.