The evolution of fungi has been going on since fungi diverged from other life around 1.5 billion years ago,  with the glomaleans branching from the "higher fungi" at ~570 million years ago, according to DNA analysis. (Schüssler et al., 2001; Tehler et al., 2000) Fungi probably colonized the land during the Cambrian, over 500 million years ago, (Taylor & Osborn, 1996) but terrestrial fossils only become uncontroversial and common during the Devonian, 400 million years ago.
A rich diversity of fungi is known from the lower Devonian Rhynie chert; an earlier record is absent. Since fungi do not biomineralise, they do not readily enter the fossil record; there are only three claims of early fungi. One from the Ordovician has been dismissed on the grounds that it lacks any distinctly fungal features, and is held by many to be contamination; the position of a "probable" Proterozoic fungus is still not established, and it may represent a stem group fungus. There is also a case for a fungal affinity for the enigmatic microfossil Ornatifilum. Since the fungi form a sister group to the animals, the two lineages must have diverged before the first animal lineages, which are known from fossils as early as the Ediacaran.
In contrast to plants and animals, the early fossil record of the fungi is meager. Factors that likely contribute to the under-representation of fungal species among fossils include the nature of fungal fruiting bodies, which are soft, fleshy, and easily degradable tissues and the microscopic dimensions of most fungal structures, which therefore are not readily evident. Fungal fossils are difficult to distinguish from those of other microbes, and are most easily identified when they resemble extant fungi. Often recovered from a permineralized plant or animal host, these samples are typically studied by making thin-section preparations that can be examined with light microscopy or transmission electron microscopy.Compression fossils are studied by dissolving the surrounding matrix with acid and then using light or scanning electron microscopy to examine surface details.
The earliest fossils possessing features typical of fungi date to the Paleoproterozoic era, some 2,400 million years ago (Ma); these multicellular benthic organisms had filamentous structures capable of anastomosis, in which hyphal branches recombine. Other recent studies (2009) estimate the arrival of fungal organisms at about 760–1060 Ma on the basis of comparisons of the rate of evolution in closely related groups. For much of the Paleozoic Era (542–251 Ma), the fungi appear to have been aquatic and consisted of organisms similar to the extant Chytrids in having flagellum-bearing spores.Phylogenetic analyses suggest that the flagellum was lost early in the evolutionary history of the fungi, and consequently, the majority of fungal species lack a flagellum. The evolutionary adaptation from an aquatic to a terrestrial lifestyle necessitated a diversification of ecological strategies for obtaining nutrients, including parasitism, saprobism, and the development of mutualistic relationships such as mycorrhiza and lichenization. Recent (2009) studies suggest that the ancestral ecological state of the Ascomycota was saprobism, and that independent lichenization events have occurred multiple times.
Lichen-like fossils have been found in the Doushantuo Formation in southern China dating back to 635–551 Ma. Lichens were a component of the early terrestrial ecosystems, and the estimated age of the oldest terrestrial lichen fossil is 400 Ma; this date corresponds to the age of the oldest known sporocarp fossil, a Paleopyrenomycites species found in the Rhynie Chert. The oldest fossil with microscopic features resembling modern-day basidiomycetes is Palaeoancistrus, found permineralized with a fern from the Pennsylvanian. Rare in the fossil record are the homobasidiomycetes (a taxon roughly equivalent to the mushroom-producing species of the agaricomycetes). Two amber-preserved specimens provide evidence that the earliest known mushroom-forming fungi (the extinct species Archaeomarasmius legletti) appeared during the mid-Cretaceous, 90 Ma.
Some time after the Permian-Triassic extinction event (251.4 Ma), a fungal spike (originally thought to be an extraordinary abundance of fungal spores in sediments) formed, suggesting that fungi were the dominant life form at this time, representing nearly 100% of the available fossil record for this period. However, the relative proportion of fungal spores relative to spores formed by algal species is difficult to assess, the spike did not appear worldwide, and in many places it did not fall on the Permian-Triassic boundary.
65 million years ago, immediately after the Cretaceous-Tertiary (K-T) extinction that famously killed off most dinosaurs, there is a dramatic increase in evidence of fungi, apparently the death of most plant and animal species leading to a huge fungal bloom like "a massive compost heap". The lack of K-T extinction in fungal evolution is also supported by molecular data, because phylogenetic comparative analyses of a tree consist of 5,284 mushroom species (Agaricomycetes) didn't show signal for mass a extinction event around the Cretaceous-Tertiary boundary.
^Wang, D.Y.C.; Kumar, S.; Hedges, S.B. (1999). "Divergence time estimates for the early history of animal phyla and the origin of plants, animals and fungi". Proceedings of the Royal Society of London B. 266: 163–171. doi:10.1098/rspb.1999.0617.
^Schoch CL; Sung G-H; López-Giráldez F; et al. (2009). "The Ascomycota tree of life: A phylum-wide phylogeny clarifies the origin and evolution of fundamental reproductive and ecological traits". Systematic Biology. 58 (2): 224–39. doi:10.1093/sysbio/syp020. PMID20525580.
^Taylor TN, Taylor EL (1996). "The distribution and interactions of some Paleozoic fungi". Review of Palaeobotany and Palynology. 95 (1–4): 83–94. doi:10.1016/S0034-6667(96)00029-2.
^Dotzler N, Walker C, Krings M, Hass H, Kerp H, Taylor TN, Agerer R (2009). "Acaulosporoid glomeromycotan spores with a germination shield from the 400-million-year-old Rhynie chert". Mycological Progress. 8 (1): 9–18. doi:10.1007/s11557-008-0573-1. hdl:1808/13680.
^Karatygin IV, Snigirevskaya NS, Vikulin SV (2009). "The most ancient terrestrial lichen Winfrenatia reticulata: A new find and new interpretation". Paleontological Journal. 43 (1): 107–14. doi:10.1134/S0031030109010110.
^Hibbett DS, Grimaldi D, Donoghue MJ (1997). "Fossil mushrooms from Miocene and Cretaceous ambers and the evolution of homobasidiomycetes". American Journal of Botany. 84 (7): 981–91. doi:10.2307/2446289. JSTOR2446289.
^Foster CB, Stephenson MH, Marshall C, Logan GA, Greenwood PF (2002). "A revision of Reduviasporonites Wilson 1962: description, illustration, comparison and biological affinities". Palynology. 26 (1): 35–58. doi:10.2113/0260035.
^López-Gómez J, Taylor EL (2005). "Permian-Triassic transition in Spain: a multidisciplinary approach". Palaeogeography, Palaeoclimatology, Palaeoecology. 229 (1–2): 1–2. doi:10.1016/j.palaeo.2005.06.028.