Paleoclimate records from glacial Indian and Pacific oceans sediments document millennial-scale fluctuations of subsurface dissolved oxygen levels and denitrification coherent with North Atlantic temperature oscillations. Yet the mechanism of this teleconnection between the remote ocean basins remains elusive. Here we present model simulations of the oxygen and nitrogen cycles that explain how changes in deepwater subduction in the North Atlantic can cause large and synchronous variations of oxygen minimum zones throughout the Northern Hemisphere of the Indian and Pacific oceans, consistent with the paleoclimate records. Cold periods in the North Atlantic are associated with reduced nutrient delivery to the upper Indo-Pacific oceans, thereb...