The global-scale oxygenation of Earth’s surface represents one of the most fundamental chemical transformations in our planet’s history. There is empirical and theoretical evidence for at least two distinct and stable regimes of Earth surface oxygenation—a ‘low-O2 world’ characterized by pervasively reducing deep ocean waters, and a ‘high-O2 world’ with dominantly well-oxygenated deep ocean waters represented by our modern surface environment. Numerous biogeochemical processes and feedbacks control the redox state of the marine system, particularly when considered globally and on geologic timescales. It has therefore proven challenging to provide quantitative and internally consistent estimates of the atmospheric oxygen levels (and thereby, productivity, nutrient availability, and reductant consumption) necessary to oxygenate the deep seas. Here, we leverage an Earth-system biogeochemical model that tracks the carbon, nitrogen, oxygen, phosphorus, and sulfur cycles (CANOPS) to provide new quantitative constraints on this relationship. We explore ocean biogeochemistry and fluxes of reduced carbon to the seafloor across a wide range of atmospheric oxygen levels from 0.01 – 100% of the present atmospheric level (PAL), and implement a stochastic approach to provide formal estimates of uncertainty on our results. We find that deep ocean waters remain largely reducing, and ocean productivity remains significantly muted relative to the modern marine biosphere, until pO2 levels reach ~40% PAL. These results have major implications for quantitative constraints on atmospheric pO2 levels during the latest Proterozoic and Paleozoic, both in terms of environmental habitability for early animals and with respect to potential energetic constraints on growing and diversifying benthic communities.