Males and females of the same species are known to differ at least in some cognitive domains, but such differences are not systematic across species. As a consequence, it remains unclear whether reported differences generally reflect adaptive adjustments to diverging selective pressures, or whether differences are mere side products of physiological differences necessary for reproduction. Here, we show that sex differences in cognition occur even in a sex-changing species, a protogynous hermaphroditic species where all males have previously been females. We tested male and female cleaner fish Labroides dimidiatus in four cognitive tasks to evaluate their learning and inhibitory control abilities first in an abstract presentation of the tasks, then in more ecologically relevant contexts. The results showed that males were better learners than females in the two learning tasks (i.e. reversal learning as an abstract task and a food quantity assessment task as an ecologically relevant task). Conversely, females showed enhanced abilities compared with males in the abstract inhibitory control task (i.e. detour task); but both sexes performed equally in the ecologically relevant inhibitory control task (i.e. ‘audience effect’ task). Hence, sex-changing species may offer unique opportunities to study proximate and/or ultimate causes underlying sex differences in cognitive abilities.