Symbiosis—the close and often long-term interaction of species—is predicted to drive genome evolution in a variety of ways. For example, parasitic interactions have been shown to increase rates of molecular evolution, a trend generally attributed to the Red Queen Hypothesis. However, it is much less clear how mutualisms impact the genome, as both increased and reduced rates of change have been predicted. Here we sequence the genomes of seven species of ants, three that have convergently evolved obligate plant–ant mutualism and four closely related species of non-mutualists. Comparing these sequences, we investigate how genome evolution is shaped by mutualistic behaviour. We find that rates of molecular evolution are higher in the mutualists genome wide, a characteristic apparently not the result of demography. Our results suggest that the intimate relationships of obligate mutualists may lead to selective pressures similar to those seen in parasites, thereby increasing rates of evolution.