Compared to life in the water, life on land got off to a decidedly slow start. The seas had been swarming with life for hundreds of millions of years before the first tentative colonisation of the previously barren continents by small algae and plants in the Ordovician about 470 million years ago. Even then, it wasn't until about the middle part of the Silurian, about 430 million years ago (give or take) that the first vascular plants and anything bigger than a moss put in an appearance. These early plants were still small by modern standards - one of the larger forms, Cooksonia, was practically a giant at heights of nearly a metre. The first really large land organism made its imposing appearance in the late Silurian.
Reaching heights of up to eight metres, Prototaxites would have loomed over anything else around at the time - something that is made pretty clear in the reconstruction above from Hueber (2001) (obtained via Hans Steur's palaeobotany page, which has a far better analysis of Prototaxites than I'm about to give you). Prototaxites is known from fossils reminiscent of the trunk of a tree, and was originally described as such in 1859. However, the internal structure of Prototaxites is very different from that of any tree. Rather than the vascular cells of a tree, Prototaxites is composed of long filamentous tubes - large unbranched tubes that probably supplied structural support, and much smaller multi-branched tubes that ran among and around the skeletal filaments and probably held the structure together. This structure was compared to the filamentous structure of a number of modern algae, and for many years Prototaxites was considered a giant alga, probably related to the modern brown algae.
However, all known algae are aquatic, while Prototaxites was found in association with terrestrial organisms and was undoubtedly terrestrial itself. In cross-section Prototaxites also lacks the orderliness of structure found in brown algae, with filaments arranged randomly in the trunk with no clear division between pith and cortex. Hueber (2001) therefore made the suggestion that instead of being an alga, Prototaxites might be a gigantic fungus. He compared it to the living perennial bracket fungi, which have a rigid structure and can also reach notable sizes (up to a metre in diameter) through cumulative growth over many years.
The main barrier to accepting Prototaxites as a fungus lies in the size of the filaments (which would then be hyphae). The skeletal filaments reach a diameter of up to 50μm while modern fungi will rarely be more than 10μm. The other major issue, of course, is its size overall. Where did such a large saprobic fungus gain its nutrients from? Despite the plausability of Hueber's (2001) model of perennial growth, and his comparison with the gigantic size attained by hyphal masses in other modern fungi such as a specimen of Armillaria bulbosa covering an area of 15ha, Selosse (2002) pointed out that the modern taxa live in an environment with a much larger overall biomass. A purely saprobic Prototaxites would have required far more nutrition than could be supplied by the meagre vegetation of the Silurian. Selosse (2002) therefore suggested that, rather than being purely fungal, Prototaxites might have been a photosynthetic lichen-like symbiosis. The large skeletal filaments, he suggested, might still represent an algal form, contained and protected by the surrounding fungal hyphae. The idea of an eight-metre-tall lichen is still pretty amazing, but not incredible when we consider that there would have been relatively little competition in the Silurian compared to the modern environment. Prototaxites may have been a slow and inefficient grower, but there was little to exclude it. Hueber (2001) identified supposed reproductive structures on Prototaxites that he held indicated a position for it among the basidiomycetes, which include the bracket fungi. However, as pointed out by Selosse (2002), the reproductive nature of these structures is unconvincing.
No convincing evidence has been found for branching in Prototaxites. Many authors interpreting Prototaxites as a plant or alga have suggested that the flattened fossil Nematothallus found in the same deposits, which also has a filamentous structure, might represent leaves or leaf-like appendages of Prototaxites. However, the two have never been found directly attached. Graham et al. (2004) noted a similarity between Nematothallus and semi-decayed modern liverworts, and suggested that Nematothallus might belong to the latter group.
Prototaxites was around for about 50 million years, a quite impressive amount of time, but it eventually became extinct during the Devonian. Perhaps as the terrestrial environment increased in complexity, the window of low competition that Prototaxites had occupied closed. More efficient plants supplanted Prototaxites, while increased numbers of herbivores may have eaten down growing hyphae faster than the organism could regrow them. Prototaxites' time had come to a close.