Human activities have altered the global nitrogen (N) cycle, and as a result, elevated N inputs are causing profound ecological changes in diverse ecosystems. The evolutionary consequences of this global change have been largely ignored even though elevated N inputs are predicted to cause mutualism breakdown and the evolution of decreased cooperation between resource mutualists. Using a long-term (22 years) N-addition experiment, we find that elevated N inputs have altered the legume–rhizobium mutualism (where rhizobial bacteria trade N in exchange for photosynthates from legumes), causing the evolution of less-mutualistic rhizobia. Plants inoculated with rhizobium strains isolated from N-fertilized treatments produced 17–30% less biomass and had reduced chlorophyll content compared to plants inoculated with strains from unfertilized control plots. Because the legume–rhizobium mutualism is the major contributor of naturally fixed N to terrestrial ecosystems, the evolution of less-cooperative rhizobia may have important environmental consequences.