Multi-year droughts have severe environmental and economic impacts, but the instrumental record is too short to characterise multi-year drought variability. We assessed the nature of Australian multi-year droughts using simulations of the past millennium from 11 climate models. We show that multi-decadal megadroughts are a natural feature of the Australian hydroclimate. Human-caused climate change is also driving a tendency towards longer droughts in eastern and southwestern Australia.