The partial pressure of oxygen in Earth's atmosphere has increased dramatically through time, and this increase is thought to have occurred in two rapid steps at both ends of the Proterozoic Eon (∼2.5-0.543 Ga). However, the trajectory and mechanisms of Earth's oxygenation are still poorly constrained, and little is known regarding attendant changes in ocean ventilation and seafloor redox. We have a particularly poor understanding of ocean chemistry during the mid-Proterozoic (∼1.8-0.8 Ga). Given the coupling between redox-sensitive trace element cycles and planktonic productivity, various models for mid-Proterozoic ocean chemistry imply different effects on the biogeochemical cycling of major and trace nutrients, with potential ecological constraints on emerging eukaryotic life. Here, we exploit the differing redox behavior of molybdenum and chromium to provide constraints on seafloor redox evolution by coupling a large database of sedimentary metal enrichments to a mass balance model that includes spatially variant metal burial rates. We find that the metal enrichment record implies a Proterozoic deep ocean characterized by pervasive anoxia relative to the Phanerozoic (at least ∼30-40% of modern seafloor area) but a relatively small extent of euxinic (anoxic and sulfidic) seafloor (less than ∼1-10% of modern seafloor area). Our model suggests that the oceanic Mo reservoir is extremely sensitive to perturbations in the extent of sulfidic seafloor and that the record of Mo and chromium enrichments through time is consistent with the possibility of a Mo-N colimited marine biosphere during many periods of Earth's history.