Records of diagenetically mineralized, filamentous, cavity-dwelling microorganisms extend back to strata from the early Paleoproterozoic (2400 Ma). In North Greenland (Laurentia), they are first known from the Ediacaran (Neoproterozoic; ca. 600 Ma) Portfjeld Formation of southern Peary Land, in association with a biota similar to that of the Doushantuo Formation of China. The Portfjeld Formation cavity dwellers are compared with more widespread occurrences in Cambrian (Series 2, Stage 4, Miaolingian Series) strata from the same region in which assemblages in postmortal shelter structures within articulated acrotretoid brachiopods and other invertebrates are common. All specimens were recovered by digestion of carbonate samples in weak acids. The described fossils are preserved as mineral encrusted threads but this diagenetic phosphatization unfortunately obscures their biological identity.