The Australian-Indonesian monsoon is an important component of the climate system in the tropical Indo-Pacific region1. However, its past variability, relation with northern and southern high-latitude climate and connection to the other Asian monsoon systems are poorly understood. Here we present high-resolution records of monsoon-controlled austral winter upwelling during the past 22,000 years, based on planktic foraminiferal oxygen isotopes and faunal composition in a sedimentary archive collected offshore southern Java. We show that glacial-interglacial variations in the Australian-Indonesian winter monsoon were in phase with the Indian summer monsoon system, consistent with their modern linkage through cross-equatorial surface winds. Likewise, millennial-scale variability of upwelling shares similar sign and timing with upwelling variability in the Arabian Sea. On the basis of element composition and grain-size distribution as precipitation-sensitive proxies in the same archive, we infer that (austral) summer monsoon rainfall was highest during the Bølling-Allerød period and the past 2,500 years. Our results indicate drier conditions during Heinrich Stadial 1 due to a southward shift of summer rainfall and a relatively weak Hadley cell south of the Equator. We suggest that the Australian-Indonesian summer and winter monsoon variability were closely linked to summer insolation and abrupt climate changes in the northern hemisphere.