The microfossil Frutexites is known from many Palaeozoic and some Proterozoic carbonate sedimentary rocks. We recently found unusually well-preserved examples in the early Proterozoic Gunflint Iron Formation of Ontario, Canada. These are preserved in chert, along with other microfossils of the Gunflint microbiota. The Gunflint examples have previously been described as laminated, columnar-branching microstromatolites. We have found narrow tubes (interpreted as trichome moulds) axially placed in many of the microcolumns. By comparison with extant organisms, we interpret Frutexites as a thick-sheathed scytonematacean cyanophyte. These are the oldest known fossil scytonemataceans. They apparently grew within mats of other microorganisms. These probably were photosynthetic organisms, which may have significant implications in the interpretation of some occurrences, such as in the fore-reef facies of Devonian reefs in Western Australia.