Theoretical and experimental studies have shown that high mutation rates can be advantageous, especially in novel or fluctuating environments. Here we examine how frequency-dependent competition may lead to fluctuations in trait frequencies that exert upward selective pressure on mutation rates. We use a mathematical model to show that cyclical trait dynamics generated by "rock-paper-scissors" competition can cause the mutation rate in a population to converge to a high evolutionarily stable mutation rate, reflecting a trade-off between generating novelty and reproducing past success. Introducing recombination lowers the evolutionarily stable mutation rate but allows stable coexistence between mutation rates above and below the evolutionarily stable rate. Even considering strong mutational load and ignoring the costs of faithful replication, evolution favors positive mutation rates if the selective advantage of prevailing in competition exceeds the ratio of recombining to nonrecombining offspring. We discuss a number of genomic mechanisms that may meet our theoretical requirements for the adaptive evolution of mutation. Overall, our results suggest that local mutation rates may be higher on genes influencing cyclical competition and that global mutation rates in asexual species may be higher in populations subject to strong cyclical competition.