Executive functions are a set of cognitive control processes required for optimizing goal-directed behavior. Despite more than two centuries of research on executive functions, mostly in humans and nonhuman primates, there is still a knowledge gap in what constitutes the mechanistic basis of evolutionary variation in executive function abilities. Here, we show experimentally that size changes in a forebrain structure (i.e. telencephalon) underlie individual variation in executive function capacities in a fish. For this, we used male guppies (Poecilia reticulata) issued from artificial selection lines with substantial differences in telencephalon size relative to the rest of the brain. We tested fish from the up- and down-selected lines not only in three tasks for the main core executive functions: cognitive flexibility, inhibitory control, and working memory, but also in a basic conditioning test that does not require executive functions. Individuals with relatively larger telencephalons outperformed individuals with smaller telencephalons in all three executive function assays but not in the conditioning assay. Based on our findings, we propose that the telencephalon is the executive brain in teleost fish. Together, it suggests that selective enlargement of key brain structures with distinct functions, like the fish telencephalon, is a potent evolutionary pathway toward evolutionary enhancement of advanced cognitive abilities in vertebrates.