The first 2 b.y. of Earth’s history was an important time for life when microbes evolved and diversified into essentially all of the metabolic forms that now exist. Because of feedbacks between biology and the surface environment, understanding Earth’s biological history can help us understand the evolution of Earth itself. The morphological and geochemical evidence for this ancient biological history is sparse but is increasing. Here we report evidence for 2.52 Ga exceptionally large, organic, smooth-walled, coccoidal microfossils preserved in a deep-water black chert in the Gamohaan Formation of the Kaapvaal craton of South Africa. These fossils occur mainly as compressed solitary coccoids that range in size from 20 to 265 µm but occasionally occur in short chains of cells. Morphologically these fossils are similar to Proterozoic and Phanerozoic acritarchs and to certain Archean fossils interpreted as possible cyanobacteria. However, their exceptionally large size, simple cell wall microstructure, and paleoecological setting, as well as multiple sulfur isotope systematics of pyrite within the unit, suggest that the Gamohaan Formation fossils were sulfur-oxidizing bacteria similar to those of the modern genus Thiomargarita, organisms that live in anoxic and sulfidic deep-water settings. These are the oldest reported fossil sulfur bacteria and reveal a diversity of life and ecosystems, previously only interpreted from geochemical proxies, just prior to the Great Oxidation Event, a time of major atmospheric evolution.