Interactions between fungi and plants, including parasitism, mutualism, and saprotrophy, have been invoked as key to their respective macroevolutionary success. Here we evaluate the origins of plant-fungal symbioses and saprotrophy using a time-calibrated phylogenetic framework that reveals linked and drastic shifts in diversification rates of each kingdom. Fungal colonization of land was associated with at least two origins of terrestrial green algae and preceded embryophytes (as evidenced by losses of fungal flagellum, ca. 720 Ma), likely facilitating terrestriality through endomycorrhizal and possibly endophytic symbioses. The largest radiation of fungi (Leotiomyceta), the origin of arbuscular mycorrhizae, and the diversification of extant embryophytes occurred ca. 480 Ma. This was followed by the origin of extant lichens. Saprotrophic mushrooms diversified in the Late Paleozoic as forests of seed plants started to dominate the landscape. The subsequent diversification and explosive radiation of Agaricomycetes, and eventually of ectomycorrhizal mushrooms, were associated with the evolution of Pinaceae in the Mesozoic, and establishment of angiosperm-dominated biomes in the Cretaceous.