Biased mutation spectra are pervasive, with wide variation in the magnitude of mutational biases that influence genome evolution and adaptation. How do such diverse biases evolve? Our experiments show that changing the mutation spectrum allows populations to sample previously undersampled mutational space, including beneficial mutations. The resulting shift in the distribution of fitness effects is advantageous: Beneficial mutation supply and beneficial pleiotropy both increase, while deleterious load reduces. More broadly, simulations indicate that reducing or reversing the direction of a long-term bias is always selectively favored. Such changes in mutation bias can occur easily via altered function of DNA repair genes. A phylogenetic analysis shows that these genes are repeatedly gained and lost in bacterial lineages, leading to frequent bias shifts in opposite directions. Thus, shifts in mutation spectra may evolve under selection and can directly alter the outcome of adaptive evolution by facilitating access to beneficial mutations.