Foraminifera are an ecologically important group of modern heterotrophic amoeboid eukaryotes whose naked and testate ancestors are thought to have evolved ∼1 Ga ago. However, the single-chambered agglutinated tests of these protists appear in the fossil record only after ca. 580 Ma, coinciding with the appearance of macroscopic and mineralized animals. Here we report the discovery of small, slender tubular microfossils in the Sturtian (ca. 716–635 Ma) cap carbonate of the Rasthof Formation in Namibia. The tubes are 200–1300 μm long and 20–70 μm wide, and preserve apertures and variably wide lumens, folds, constrictions, and ridges. Their sometimes flexible walls are composed of carbonaceous material and detrital minerals. This combination of morphologic and compositional characters is also present in some species of modern single-chambered agglutinated tubular foraminiferans, and is not found in other agglutinated eukaryotes. The preservation of possible early Foraminifera in the carbonate rocks deposited in the immediate aftermath of Sturtian low-latitude glaciation indicates that various morphologically modern protists thrived in microbially dominated ecosystems, and contributed to the cycling of carbon in Neoproterozoic oceans much before the rise of complex animals.