Oceanic sulfate concentrations are widely thought to have reached millimolar levels during the Proterozoic Eon, 2.5 to 0.54 billion years ago. Yet the magnitude of the increase in seawater sulfate concentrations over the course of the Eon remains largely unquantified. A rise in seawater sulfate concentrations has been inferred from the increased range of marine sulfide δ34S values following the Great Oxidation Event and was induced by two processes: enhanced oxidative weathering of sulfides on land, and the onset of marine sulfur redox cycling. Here we use mass balance and diagenetic reaction-transport models to reconstruct the sulfate concentrations in Proterozoic seawater. We find that sulfate concentrations remained below 400 µM, and were possibly as low as 100 µM, throughout much of the Proterozoic. At these low sulfate concentrations, relatively large sulfate–pyrite sulfur isotope differences cannot be explained by sulfate reduction alone and are only possible through oxidative sediment sulfur cycling. This requires oxygen concentrations of at least 10 µM in shallow Proterozoic seawater, which translates to 1–10% of present atmospheric oxygen concentrations. At these oxygen and sulfate concentrations, the oceans would have been a substantial source of methane to the atmosphere (60–140 Tmol yr−1). This methane would have accumulated to high concentrations (more than 25 ppmv) and supported greenhouse warming during much of the Proterozoic Eon, with notable exceptions during the Palaeoproterozoic and Neoproterozoic eras.