The ‘social brain hypothesis’ proposes a causal link between social complexity and either brain size or the size of key brain parts known to be involved in cognitive processing and decision-making. While previous work has focused on comparisons between species, how social complexity affects plasticity in brain morphology at the intraspecific level remains mostly unexplored. A suitable study model is the mutualist ‘cleaner’ fish Labroides dimidiatus, a species that removes ectoparasites from a variety of ‘client’ fishes in iterative social interactions. Here, we report a positive relationship between the local density of cleaners, as a proxy of both intra- and interspecific sociality, and the size of the cleaner’s brain parts suggested to be associated with cognitive functions, such as the diencephalon and telencephalon (that together form the forebrain). In contrast, the size of the mesencephalon, rhombencephalon, and brain stem, assumed more basal in function, were independent of local fish densities. Selective enlargement of brain parts, that is mosaic brain adjustment, appears to be driven by population density in cleaner fish.