Prototaxites was the first giant organism to live on the terrestrial surface, represented by columnar fossils of up to eight meters from the Early Devonian. However, its systematic affinity has been debated for over 165 years. There are now two remaining viable hypotheses: Prototaxites was either a fungus, or a member of an entirely extinct lineage. Here, we investigate the affinity of Prototaxites by contrasting its organization and molecular composition with that of Fungi. We report that fossils of Prototaxites taiti from the 407-million-year-old Rhynie chert were chemically distinct from contemporaneous Fungi and structurally distinct from all known Fungi. This finding casts doubt upon the fungal affinity of Prototaxites, instead suggesting that this enigmatic organism is best assigned to an entirely extinct eukaryotic lineage.