The Interdecadal Pacific Oscillation (IPO) influences multidecadal drought risk across the Pacific, but there are no millennial-length, high resolution IPO reconstructions for quantifying long-term drought risk. In Australia, drought risk increases in positive phases of the IPO, yet few suitable rainfall proxies and short (~100 y) instrumental records mean large uncertainties remain around drought frequency and duration. Likewise, it is unknown whether mega-droughts have occurred in Australia's past. In this study, an atmospheric teleconnection in the Indian Ocean mid-latitudes linking East Antarctica and Australia is exploited to produce the first accurate, annually dated millennial-length IPO reconstruction from the Law Dome (East Antarctica) ice core. Combined with an eastern Australian rainfall proxy from Law Dome, the first millennial-length Australian mega-drought (>5 y duration) reconstruction is presented. Eight mega-droughts are identified including one 39 y drought (AD 1174–1212), which occurred during an unprecedented century of aridity (AD 1102–1212).