Over the last 60,000 years, Sahul witnessed the first wave of global megafauna extinctions. The causes have long been debated: climate change, human impact, or a combination of both.We have mapped extinction and human arrival patterns across south-eastern Australia, revealing that in about 80% of the region, humans and megafauna coexisted for millennia. Extinction patterns were best explained by human presence and water access, with arid regions driving additional losses.