Recent studies have proposed that millennial-scale reorganization of the ocean-atmosphere circulation drives increased upwelling in the Southern Ocean, leading to rising atmospheric carbon dioxide levels and ice age terminations. Southward migration of the global monsoon is thought to link the hemispheres during deglaciation, but vital evidence from the southern sector of the vast Australasian monsoon system is yet to emerge. Here we present a 230thorium-dated stalagmite oxygen isotope record of millennial-scale changes in Australian-Indonesian monsoon rainfall over the last 31,000 years. The record shows that abrupt southward shifts of the Australian-Indonesian monsoon were synchronous with North Atlantic cold intervals 17,600-11,500 years ago. The most prominent southward shift occurred in lock-step with Heinrich Stadial 1 (17,600-14,600 years ago), and rising atmospheric carbon dioxide. Our findings show that millennial-scale climate change was transmitted rapidly across Australasia and lend support to the idea that the 3,000-year-long Heinrich 1 interval could have been critical in driving the last deglaciation.