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 years) instrumental records mean large uncertainties remain around drought frequency and duration. Likewise, it is unknown whether megadroughts have occurred in Australia’s past. In this study, an atmospheric teleconnection in the Indian Ocean midlatitudes 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 megadrought (>5 year duration) reconstruction is presented. Eight megadroughts are identified including one 39 year drought (A.D. 1174–1212), which occurred during an unprecedented century of aridity (A.D. 1102–1212).