Fossil at right is 12 cm in diameter (a small example) and was collected in the Netherlands.
Fungi are neat organisms, belonging to their own phylum separate from animals and plants. While the study of fungi (mycology) is usually done by botanists, genetic studies have shown that fungi are more closely related, evolutionarily, to animals. One of the problems of fungi is that they lack hard parts so don't leave a good fossil record making it problematic to follow their evolutionary development through geologic time.
Prototaxites is a notable exception to the lack of fungal fossils and dates from the Silurian and Devonian Periods (420 to 370 million years ago). It's also quite unusual (for a fungus) in having a trunk-like structure that was about a meter in diameter (3 ft) and up to 8 meters in height (26 ft). This trunk or stalk was made up of tiny interwoven fibers only 50 microns (0.0020 in) in diameter. Some have suggested it also had an algal symbiont which would technically make it a lichen.
Digging up a Prototaxites in Saudi Arabia
What's amazing about these fungi is that they were, by far, the tallest organisms on Earth at the time. During the Silurian and early Devonian Periods, plant life primarily consisted of non-vascular plants like mosses (bryophytes) and some primitive vascular plants (trachyophytes) that, at most, reached a meter in height. The most advanced terrestrial animal life consisted of invertebrates like insects and eventually a few early amphibians. Prototaxites towered over them all dominating the landscape.
Painting of Prototaxites by Mary Parrish, National Museum of Natural History
It would have been a truly alien landscape. Read more about the research here.