Anthropogenic global warming affects marine ecosystems in complex ways, and declining ocean oxygenation is a growing concern. Forecasting the geographical and bathymetric extent, rate and intensity of future deoxygenation and its effects on oceanic biota, however, remains highly challenging because of the complex feedbacks in the earth-ocean-biota system. Information on past global warming events such as the Paleocene Eocene Thermal Maximum (PETM, ~55.5 Ma), a potential analog for present and future global warming, may help in such forecasting. Documenting past ocean deoxygenation, however, is hampered by the lack of sensitive proxies for past oceanic oxygen levels throughout the water column. As yet no evidence has been presented for pervasive deoxygenation in the upper water column through expansion of Oxygen Minimum Zones (OMZs). We apply a novel proxy for paleo-redox conditions, the iodine to calcium ratio (I/Ca) in bulk coarse fraction sediment and planktic foraminiferal tests from pelagic sites in different oceans, and compared our reconstruction with modeled oxygen levels. The reconstructed iodate gradients indicate that deoxygenation occurred in the upper water column in the Atlantic, Indian Oceans, and possibly the Pacific Ocean as well during the PETM, due to vertical and potentially lateral expansion of OMZs.