A major component of Darwin's formulation of sexual selection theory is whether mate choice can contribute to the evolution of cognitive abilities. Although a correlation between cognition and attractive traits has commonly been reported, the processes that generate such associations remain elusive. Here, we investigated female preference, neophobia and spatial learning in the sailfin tetra, Crenuchus spilurus, a sexually dimorphic fish. Females chose the most ornamented males, which were also more neophobic. This is in line with the asset protection principle, which posits that attractive males should be more cautious because of their higher prospective fitness returns. After repeated exposure, more ornamented males learnt to navigate the complex maze faster, with chosen (and highest ornamented) males showing higher accuracy to solve the maze on the last day of trials. Because the asset protection principle stems from predation pressure, we propose that sexual selection through female mate choice creates a risk–reward trade-off, upon which natural selection acts by indirectly increasing learning abilities. As such, sexual selection forms the substrate, but natural selection drives enhanced cognitive abilities in attractive C. spilurus males.