Mycorrhizae, the symbiotic associations of plant roots and fungal hyphae, are classic examples of mutualisms. In these ecologically important associations, the fungi derive photosynthetic sugars from their plant hosts, which in turn benefit from fungus-mediated uptake of mineral nutrients. Early views on the evolution of symbioses suggested that all long-term, intimate associations tend to evolve toward mutualism. Following this principle, it has been suggested that mycorrhizal symbioses are the stable derivatives of ancestral antagonistic interactions involving plant parasitic fungi. Alternatively, mutualisms have been interpreted as inherently unstable reciprocal parasitisms, which can be disrupted by conflicts of interest among the partners. To determine the number of origins of mycorrhizae, and to assess their evolutionary stability, it is necessary to understand the phylogenetic relationships of the taxa involved. Here we present a broad phylogenetic analysis of mycorrhizal and free-living homobasidiomycetes (mushroom-forming fungi). Our results indicate that mycorrhizal symbionts with diverse plant hosts have evolved repeatedly from saprotrophic precursors, but also that there have been multiple reversals to a free-living condition. These findings suggest that mycorrhizae are unstable, evolutionarily dynamic associations.