Background: Plasticity in brain size and the size of different brain regions during early ontogeny is known from many vertebrate taxa, but less is known about plasticity in the brains of adults. In contrast to mammals and birds, most parts of a fish’s brain continue to undergo neurogenesis throughout adulthood, making lifelong plasticity in brain size possible. We tested whether maturing adult three-spined sticklebacks (Gasterosteus aculeatus) reared in a stimulus-poor environment exhibited brain plasticity in response to environmental enrichment, and whether these responses were sex-specific, thus altering the degree of sexual size dimorphism in the brain. Results: Relative sizes of total brain and bulbus olfactorius showed sex-specific responses to treatment: males developed larger brains but smaller bulbi olfactorii than females in the enriched treatment. Hence, the degree of sexual size dimorphism (SSD) in relative brain size and the relative size of the bulbus olfactorius was found to be environment-dependent. Furthermore, the enriched treatment induced development of smaller tecta optica in both sexes. Conclusions: These results demonstrate that adult fish can alter the size of their brain (or brain regions) in response to environmental stimuli, and these responses can be sex-specific. Hence, the degree of SSD in brain size can be environment-dependent, and our results hint at the possibility of a large plastic component to SSD in stickleback brains. Apart from contributing to our understanding of the processes shaping and explaining variation in brain size and the size of different brain regions in the wild, the results show that provision of structural complexity in captive environments can influence brain development. Assuming that the observed plasticity influences fish behaviour, these findings may also have relevance for fish stocking, both for economical and conservational purposes.