Biased mutation spectra are pervasive, with widely varying direction and magnitude of mutational biases that influence genome evolution and adaptation. Why are unbiased spectra rare, and how do such diverse biases evolve? We show that changing the mutation spectrum allows populations to sample previously under-sampled mutational space. The resulting shift in the distribution of fitness effects is advantageous: the beneficial mutation supply and beneficial pleiotropy increase, and deleterious load reduces. More broadly, adaptive walk simulations indicate that the evolution of a mutational bias in an unbiased ancestor is selectively neutral; but reversing the direction of a long-term bias is always selectively favoured. Indeed, spectrum changes in the bacterial phylogeny occur frequently, typically involving reversals of ancestral bias. Thus, shifts in mutation spectra evolve under selection, and can directly alter outcomes of adaptive evolution by facilitating access to beneficial mutations.