The mammalian brain comprises a number of functionally distinct systems. It might therefore be expected that natural selection on particular behavioural capacities would have caused size changes selectively, in the systems mediating those capacities. It has been claimed, however, that developmental constraints limited such mosaic evolution, causing co-ordinated size change among individual brain components. Here we analyse comparative data to demonstrate that mosaic change has been an important factor in brain structure evolution. First, the neocortex shows about a fivefold difference in volume between primates and insectivores even after accounting for its scaling relationship with the rest of the brain. Second, brain structures with major anatomical and functional links evolved together independently of evolutionary change in other structures. This is true at the level of both basic brain subdivisions and more fine-grained functional systems. Hence, brain evolution in these groups involved complex relationships among individual brain components.