I present our recent studies applying a comparative approach to understanding how brains evolved across the tree of life. Contradicting the widespread assumption that mammalian brain evolution predominantly involved expansion of frontal neocortex, results indicate complex patterns of mosaic structural change across both cortical and sub-cortical regions. Notably, the cerebellum expanded rapidly in the human lineage, changes which may have been crucial in the evolution of our facility for understanding and producing syntactically structured behaviour, including tool use and language. Postnatal development was key to these changes, helping to explain the extended period of immaturity in humans and other great apes. The complexity of the patterns of brain evolution contradict single-factor hypotheses and in particular undermine attempts to explain cognitive evolution as the product of selection on some single generalised capacity such as ‘executive control’. Instead, the results suggest that the brains of different species support specialized forms of embodied cognition closely associated with their sensory-motor adaptations.