Obligate mutualistic relationships are often inferred to be the result of higher levels of selection. However, because such mutualists consist of separate gene pools, innovative group-selected traits can only become established when they first provide a decisive fitness advantage to one of the partner species. Here we document such a sequence that was connected to a major evolutionary transition in the fungus-growing ants, when the ancestor of the derived leaf-cutting ants shifted from a diet of dry vegetative material to the almost exclusive use of freshly cut leaves. This shift generated visible adaptations in the host ants, such as increased worker dimorphism allowing large workers to cut fresh leaves, but comparative studies of the specific fungal adaptations that accompanied the transition have not been done. Here we report the first large comparative data set on enzymatic fungus garden profiles and focus on one of these enzymes, a laccase that is believed to oxidize phenols in defensive secondary plant compounds. We show that this laccase is exclusively found in the gardens of leaf-cutting ants where it can be inferred to have arisen by selection at the individual level when the ants increased the share of fresh leaves in their forage. However, once in place, this novel enzyme function gave the entire mutualism a significant colony-level advantage, which allowed the leaf-cutting ants to evolve very large long-lived colonies and to become one of the most important and widespread herbivores in neotropical ecosystems.