Large brains relative to body size represent an evolutionarily costly adaptation as they are metabolically expensive and demand substantial amounts of time to reach structural and functional maturity thereby exacerbating offspring mortality while delaying reproductive age. In spite of its cost and adaptive impact, no genomic features linked to brain evolution have been found. By conducting a genome-wide analysis in all 37 fully sequenced mammalian genomes, we show that encephalization is significantly correlated with overall protein amino acid composition. This correlation is not a by-product of changes in nucleotide content, lifespan, body size, absolute brain size or genome size; is independent of phylogenetic effects; and is not restricted to brain expressed genes. This is the first report of a relationship between this fundamental and complex trait and changes in protein AA usage, possibly reflecting the high selective demands imposed by the process of encephalization across mammalian lineages.