Sleep is a ubiquitous process that has been conserved in animals. Yet, our understanding of the functions of sleep largely derives from a few species. Sleep is considered to play an important role in mental processes, including learning and memory consolidation, but how widespread this relationship is across taxa remains unclear. Here, we test the impact of sleep disruption on the ability of the cleaner fish (Labroides dimidiatus) to both learn and remember a novel cognitive task. Sleep was disrupted by exposing a subset of fish to light at set intervals during the night. We found a significant negative relationship between sleep disruption and the ability to learn a novel task. Specifically, we found that fish in the light-disturbed sleep treatment took significantly longer and made more incorrect decisions to find a food reward, compared with the undisturbed sleep treatment. All fish were then allowed a normal sleep schedule and retested several days later to assess their ability to remember the task. In contrast to the learning phase, we observed no significant differences between the two treatment groups in remembering the food reward several days later. Our results demonstrate a negative impact of sleep disruption on performance in a cognitive challenging task that appeared to have the strongest effect when fish were first exposed to the challenge. Importantly, we show that the association between sleep and mental processes, such as learning, may be widespread across vertebrate taxa and potentially have an early origin in the evolutionary history of vertebrate animals.