A growing body of observations has revealed rapid changes in both the total inventory and the distribution of marine oxygen over the latter half of the 20th century, leading to increased interest in extending oxygenation records into the past. The use of paleo-oxygen proxies has the potential to extend the spatial and temporal range of current records, constrain pre-anthropogenic baselines, provide datasets necessary to test climate models under different boundary conditions, and ultimately understand how ocean oxygenation responds beyond decadal-scale changes. This review seeks to summarize the current state of knowledge about proxies for reconstructing Cenozoic marine oxygen: sedimentary features, sedimentary redox-sensitive trace elements and isotopes, biomarkers, nitrogen isotopes, foraminiferal trace elements, foraminiferal assemblages, foraminiferal morphometrics, and benthic foraminiferal carbon isotope gradients. Taking stock of each proxy reveals some common limitations as the majority of proxies functions best at low-oxygen concentrations, and many reflect multiple environmental drivers. We also highlight recent breakthroughs in geochemistry and proxy approaches to constraining pelagic (in addition to benthic) oxygenation that are rapidly advancing the field. In light of both the emergence of new proxies and the persistent multiple driver problem, the need for multi-proxy approaches and data storage and sharing that adhere to the principles of findability, accessibility, interoperability, and reusability (FAIR) is emphasized. Continued refinements of proxy approaches and both proxy–proxy and proxy–model comparisons are likely to support the growing needs of both oceanographers and paleoceanographers interested in paleo-oxygenation records.