Neurons are the basic computational units of the brain, but brain size is the predominant surrogate measure of brain functional capacity in comparative and cognitive neuroscience. This approach is based on the assumption that larger brains harbour higher numbers of neurons and their connections and therefore have a higher information processing capacity. However, recent studies have shown that brain mass may be less strongly correlated with neuron counts than previously thought. Till now, no experimental test has been conducted to examine the relationship between evolutionary changes in brain size and the number of brain neurons. Here we provide such a test by comparing neuron number in artificial selection lines of female guppies (Poecilia reticulata) with >15% difference in relative brain mass and numerous previously demonstrated cognitive differences. Using the isotropic fractionator, we demonstrate that large-brained females have a higher overall number of neurons than small-brained females, but similar neuronal densities. Importantly, this difference holds also for the telencephalon, a key region for cognition. Our study provides the first direct experimental evidence that selection for brain mass leads to matching changes in number of neurons and shows that brain size evolution is intimately linked to the evolution of neuron number and cognition.