Abstract The affinities of the Ediacara biota are a source of continual debate. A case can be made, however, that they represent an assortment of stem and crown group metazoans together with a large proportion of enigmatic forms that are difficult to classify and likely represent extinct multicellular evolutionary experiments. In the backdrop of these complex multicellular organisms are microbial communities, which in the absence of metazoan grazing and active bioturbating, constructed thick mat structures that dominated shallow- to deep-water paleoenvironments throughout the Mesoproterozoic and Neoproterozoic. Microbial mat communities played an important role in Ediacaran ecosystems by creating a firm substrate to which macroscopic organisms could attach. These mat structures are also presumed to have played a vital role in the preservation of soft-bodied Ediacaran fossils. Despite their importance, the study of Ediacaran microbial colonies, especially from deep-water localities well below the photic zone, is limited. As a result of taphonomic difficulties associated with the preservation of microbial colonies in siliciclastic sediments, the proper identification of microbially induced sedimentary structures (MISS) has greatly improved our understanding of Precambrian paleoecosystems. Here we present the oldest evidence of deep-water MISS from the terminal Neoproterozoic Avalon and Bonavista peninsulas of Newfoundland, Canada. Sedimentary analyses indicate that the pustular circular fossil Ivesheadia , previously regarded as a cnidarian or a degradational product, instead represents the remains of microbial colonies that occupied the sediment–water interface and resulted in distinct sedimentary structures. A second series of peculiar sedimentary structures colloquially known as “bubble trains” are believed to represent additional evidence of MISS from the Ediacaran of Newfoundland.