Cognitive abilities are crucial for survival and adaptation, enabling animals to navigate their environment, recognize predators and remember the location of food resources. However, underlying factors related to learning and memory can be energetically demanding and thus may vary depending on an individual's metabolism or aerobic capacity, potentially affecting individuals' cognitive performance. In this study, we explored the link between cognitive performance and whole-body metabolic traits, including aerobic scope (AS), maximum metabolic rate (MMR) and standard metabolic rate (SMR). European minnows, Phoxinus phoxinus, were trained over 20 days to locate a food reward in a maze. Individuals were trained in either a simple (two-door) or a complex (four-door) maze. Fish in the simpler maze had consistently higher success and a lower latency to reach the reward, suggesting the two-door maze was less cognitively challenging. We found a correlation between metabolic traits and cognitive performance traits (i.e. success and latency to reach the reward) at the end of training. However, this relationship varied depending on maze complexity. In the two-door maze, individuals with higher MMR and SMR had higher success and a lower latency to reach the reward. However, in the more complex maze, fish with lower metabolic rates (MMR and SMR) had higher success and lower latency to reach the reward. AS followed similar patterns but mostly affected the success to reach the reward. In simpler environments, having a higher metabolism may be more beneficial for cognitive performance, whereas in complex environments, having a lower metabolism may be more beneficial as it could be associated with a slower but more thorough exploration and learning process.