Dissolved oxygen (O2) is essential for most ocean ecosystems, fuelling organisms' respiration and facilitating the cycling of carbon and nutrients. Oxygen measurements have been interpreted to indicate that the ocean's oxygen-deficient zones (ODZs) are expanding under global warming1,2. However, models provide an unclear picture of future ODZ change in both the near term and the long term3-6. The paleoclimate record can help explore the possible range of ODZ changes in warmer-than-modern periods. Here we use foraminifera-bound nitrogen (N) isotopes to show that water-column denitrification in the eastern tropical North Pacific was greatly reduced during the Middle Miocene Climatic Optimum (MMCO) and the Early Eocene Climatic Optimum (EECO). Because denitrification is restricted to oxygen-poor waters, our results indicate that, in these two Cenozoic periods of sustained warmth, ODZs were contracted, not expanded. ODZ contraction may have arisen from a decrease in upwelling-fuelled biological productivity in the tropical Pacific, which would have reduced oxygen demand in the subsurface. Alternatively, invigoration of deep-water ventilation by the Southern Ocean may have weakened the ocean's 'biological carbon pump', which would have increased deep-ocean oxygen. The mechanism at play would have determined whether the ODZ contractions occurred in step with the warming or took centuries or millennia to develop. Thus, although our results from the Cenozoic do not necessarily apply to the near-term future, they might imply that global warming may eventually cause ODZ contraction.