Bromus tectorum, or cheatgrass, is native to Eurasia and widely invasive in western North America. By late spring, this annual plant has dispersed its seed and died; its aboveground biomass then becomes fine fuel that burns as frequently as once every 3-5 y in its invaded range. Cheatgrass has proven to be better adapted to fire there than many competing plants, but the contribution of its fungal symbionts to this adaptation had not previously been studied. In sampling cheatgrass endophytes, many fire-associated fungi were found, including Morchella in three western states (New Mexico, Idaho, and Washington). In greenhouse experiments, a New Mexico isolate of Morchella increased both the biomass and fecundity of its local cheatgrass population, thus simultaneously increasing both the probability of fire and survival of that event, via more fuel and a greater, belowground seed bank, respectively. Re-isolation efforts proved that Morchella could infect cheatgrass roots in a non-mycorrhizal manner and then grow up into aboveground tissues. The same Morchella isolate also increased survival of seed exposed to heat typical of that which develops in the seed bank during a cheatgrass fire. Phylogenetic analysis of Eurasian and North American Morchella revealed that this fire-associated mutualism was evolutionarily novel, in that cheatgrass isolates belonged to two phylogenetically distinct species, or phylotypes, designated Mel-6 and Mel-12 whose evolutionary origin appears to be within western North America. Mutualisms with fire-associated fungi may be contributing to the cheatgrass invasion of western North America.