Advanced cognitive abilities have long been hypothesized to be important in mating. Yet, most work on sexual selection has focused on morphological traits and its relevance for cognitive evolution is poorly understood. We studied the spatial memory of lekking long-billed hermits (Phaethornis longirostris) and evaluated its role in lek territory ownership, the magnitude of its effect compared to phenotypic traits expected to influence sexual selection, and whether its variation is indicated in the structure of mating vocal signal. Spatial memory (the ability to recall the position of a rewarding feeder) was compared between “territorial” and “floater” males. Interestingly, although spatial memory and body size both positively affected the probability of lek territory ownership, our results suggest a stronger effect of spatial memory. Bill tip length (used as weapon in agonistic interactions) also showed a positive but smaller effect. Load lifting during vertical flight, a measure of physical performance relevant to agonistic interactions, had no effect on territory ownership. Finally, both body size and spatial memory were indicated in the structure of male song: body size negatively correlated with song lowest frequency, while spatial memory positively predicted song consistency. Together, our findings lend support for cognition as a sexual selection target.