In mammals and birds, tool-using species are characterized by their relatively large telencephalon containing a higher proportion of total brain neurons compared to other species. Some teleost species in the wrasse family have evolved tool-using abilities. In this study, we compared the brains of tool-using wrasses with various teleost species. We show that in the tool-using wrasses, the telencephalon and the ventral part of the forebrain and midbrain are significantly enlarged compared to other teleost species but do not contain a larger proportion of cells. Instead, this size difference is due to large fiber tracts connecting the dorsal part of the telencephalon (pallium) to the inferior lobe, a ventral mesencephalic structure absent in amniotes. The high degree of connectivity between these structures in tool-using wrasses suggests that the inferior lobe could contribute to higher-order cognitive functions. We conclude that the evolution of non-telencephalic structures might have been key in the emergence of these cognitive functions in teleosts.