Diversified grasslands that contain native plant species can produce biofuels, support sustainable grazing systems, and produce other ecosystem services. However, ecosystem service production can be disrupted by invasion of exotic perennial plants, and these plants can have soil-microbial “legacies” that may interfere with establishment and maintenance of diversified grasslands even after effective management of the invasive species. The nature of such legacies is not well understood, but may involve suppression of mutualisms between native species and soil microbes. In this study, we tested the hypotheses that legacy effects of invasive species change colonization rates, diversity, and composition of arbuscular-mycorrhizal fungi (AMF) associated with seedlings of co-occurring invasive and native grassland species. In a glasshouse, experimental soils were conditioned by cultivating three invasive grassland perennials, three native grassland perennials, and a native perennial mixture. Each was grown separately through three cycles of growth, after which we used T-RFLP analysis to characterize AMF associations of seedlings of six native perennial and six invasive perennial species grown in these soils. Legacy effects of soil conditioning by invasive species did not affect AMF richness in seedling roots, but did affect AMF colonization rates and the taxonomic composition of mycorrhizal associations in seedling roots. Moreover, native species were more heavily colonized by AMF and roots of native species had greater AMF richness (number of AMF operational taxonomic units per seedling) than did invasive species. The invasive species used to condition soil in this experiment have been shown to have legacy effects on biomass of native seedlings, reducing their growth in this and a previous similar experiment. Therefore, our results suggest that successful plant invaders can have legacies that affect soil-microbial associations of native plants and that these effects can inhibit growth of native plant species in invaded communities.