Late Quaternary megafauna extinctions impoverished mammalian diversity worldwide. The causes of these extinctions in Australia are most controversial but essential to resolve, because this continent-wide event presaged similar losses that occurred thousands of years later on other continents. Here we apply a rigorous metadata analysis and new ensemble-hindcasting approach to 659 Australian megafauna fossil ages. When coupled with analysis of several high-resolution climate records, we show that megafaunal extinctions were broadly synchronous among genera and independent of climate aridity and variability in Australia over the last 120,000 years. Our results reject climate change as the primary driver of megafauna extinctions in the world's most controversial context, and instead estimate that the megafauna disappeared Australia-wide similar to 13,500 years after human arrival, with shorter periods of coexistence in some regions. This is the first comprehensive approach to incorporate uncertainty in fossil ages, extinction timing and climatology, to quantify mechanisms of prehistorical extinctions.