Invasive plants negatively impact native communities by altering ecosystem processes and reducing species diversity. Plants in the legume family are overrepresented among invasive taxa and establish in disturbed environments common in urban ecosystems. Mutualisms with rhizobia and anthropogenic activities, such as nitrogen fertilization, may be key mechanisms driving legume invasions of urban habitats. Moreover, legume species and genetic lineages within species may vary in their responses to nitrogen fertilization, making some more likely to invade than others. Despite this threat, it remains unclear whether nitrogen fertilization impacts mutualism and plant growth traits of invasive legumes in urban environments, and whether these effects depend on the genetic origin of invaders. We conducted a common garden experiment using two widespread, invasive legume species, Medicago sativa and Trifolium pratense, to test the effects of species, genetic origin of lineages within species, and nitrogen fertilization on the mutualism. Soil nitrogen was manipulated and effects on traits associated with the mutualism (nodule traits) and plant growth were quantified. Nitrogen fertilization improved nodule traits and host growth for both species, but M. sativa and certain genetic lineages of this species benefited more from fertilization than any of the tested T. pratense lineages. This work reveals how anthropogenic activities alter mutualism traits and plant growth in urban environments, potentially facilitating invasions by leguminous taxa. Because species and lineages varied in the strength of their responses to fertilization, over time some invading legumes may outcompete other plant species or lineages, leading to differential impacts on native communities in urban environments.