Divergence of protein sequences and gene expression patterns are two fundamental mechanisms that generate organismal diversity. Here, we have used genome and transcriptome data from eight mammals and one bird to study the positive correlation of these two processes throughout mammalian evolution. We demonstrate that the correlation is stable over time and most pronounced in neural tissues, which indicates that it is the result of strong negative selection. The correlation is not driven by genes with specific functions and may instead best be viewed as an evolutionary default state, which can nevertheless be evaded by certain gene types. In particular, genes with developmental and neural functions are skewed toward changes in gene expression, consistent with selection against pleiotropic effects associated with changes in protein sequences. Surprisingly, we find that the correlation between expression divergence and protein divergence is not explained by between-gene variation in expression level, tissue specificity, protein connectivity, or other investigated gene characteristics, suggesting that it arises independently of these gene traits. The selective constraints on protein sequences and gene expression patterns also fluctuate in a coordinate manner across phylogenetic branches: We find that gene-specific changes in the rate of protein evolution in a specific mammalian lineage tend to be accompanied by similar changes in the rate of expression evolution. Taken together, our findings highlight many new aspects of the correlation between protein divergence and expression divergence, and attest to its role as a fundamental property of mammalian genome evolution.