Eastern Australia recently experienced an intense drought (Millennium Drought, 2003-2009) and record-breaking rainfall and flooding (austral summer 2010-2011). There is some limited evidence for a climate change contribution to these events, but such analyses are hampered by the paucity of information on long-term natural variability. Analyzing a new reconstruction of summer (December-January-February) Palmer Drought Severity Index (the Australia-New Zealand Drought Atlas; ANZDA, 1500-2012 CE), we find moisture deficits during the Millennium Drought fall within the range of the last 500 years of natural hydroclimate variability. This variability includes periods of multi-decadal drought in the 1500s more persistent than any event in the historical record. However, the severity of the Millennium Drought, which was caused by autumn (March-April-May) precipitation declines, may be underestimated in the ANZDA because the reconstruction is biased towards summer and antecedent spring (September-October-November) precipitation. The pluvial in 2011, however, which was characterized by extreme summer rainfall faithfully captured by the ANZDA, is likely the wettest year in the reconstruction for Coastal Queensland. Climate projections (RCP 8.5 scenario) suggest that eastern Australia will experience long-term drying during the 21st century. While the contribution of anthropogenic forcing to recent extremes remains an open question, these projections indicate an amplified risk of multi-year drought anomalies matching or exceeding the intensity of the Millennium Drought.