Determining how variation in brain morphology affects cognitive abilities is important to understand inter-individual variation in cognition and, ultimately, cognitive evolution. Yet, despite many decades of research in this area, there is surprisingly little experimental data available from assays that quantify cognitive abilities and brain morphology in the same individuals. Here, we tested female guppies (Poecilia reticulata) in two tasks, colour discrimination and reversal learning, to evaluate their learning abilities and cognitive flexibility. We then estimated the size of five brain regions (telencephalon, optic tectum, hypothalamus, cerebellum and dorsal medulla), in addition to relative brain size. We found that optic tectum relative size, in relation to the rest of the brain, correlated positively with discrimination learning performance, while relative telencephalon size correlated positively with reversal learning performance. The other brain measures were not associated with performance in either task. By evaluating how fast learning occurs and how fast an animal adjusts its learning rules to changing conditions, we find support for that different brain regions have distinct functional correlations at the individual level. Importantly, telencephalon size emerges as an important neural correlate of higher executive functions such as cognitive flexibility. This is rare evidence supporting the theory that more neural tissue in key brain regions confers cognitive benefits.