Various geochemical records suggest that atmospheric O2 increased in the Ediacaran (635–541 Ma), broadly coincident with the emergence and diversification of large animals and increasing marine ecosystem complexity. Furthermore, geochemical proxies indicate that seawater sulfate levels rose at this time too, which has been hypothesized to reflect increased sulfide oxidation in marine sediments caused by sediment mixing of the newly evolved macrofauna. However, the exact timing of oxygenation is not yet understood, and there are claims for significant oxygenation prior to the Ediacaran. Furthermore, recent evidence suggests that physical mixing of sediments did not become important until the late Silurian. Here we report a multiple sulfur isotope record from a ca. 835–630 Ma succession from Svalbard, further supported by data from Proterozoic strata in Canada, Australia, Russia, and the United States, in order to investigate the timing of oxygenation. We present isotopic evidence for onset of globally significant bacterial sulfur disproportionation and reoxidative sulfur cycling following the 635 Ma Marinoan glaciation. Widespread sulfide oxidation helps to explain the observed first-order increase in seawater sulfate concentration from the earliest Ediacaran to the Precambrian-Cambrian boundary by reducing the amount of sulfur buried as pyrite. Expansion of reoxidative sulfur cycling to a global scale also indicates increasing environmental O2 levels. Thus, our data suggest that increasing atmospheric O2 levels may have played a role in the emergence of the Ediacaran macrofauna and increasing marine ecosystem complexity.