Climate and fire are the key environmental factors that shape the distribution and demography of plant populations in Australia. Because of limited palaeoecological records in this arid continent, however, it is unclear as to which factor impacted vegetation more strongly, and what were the roles of fire regime changes owing to human activity and megafaunal extinction (since ca 50 kya). To address these questions, we analysed historical genetic, demographic and distributional changes in a widespread conifer species complex that paradoxically grows in fire-prone regions, yet is very sensitive to fire. Genetic demographic analysis showed that the arid populations experienced strong bottlenecks, consistent with range contractions during the Last Glacial Maximum (ca 20 kya) predicted by species distribution models. In southern temperate regions, the population sizes were estimated to have been mostly stable, followed by some expansion coinciding with climate amelioration at the end of the last glacial period. By contrast, in the flammable tropical savannahs, where fire risk is the highest, demographic analysis failed to detect significant population bottlenecks. Collectively, these results suggest that the impact of climate change overwhelmed any modifications to fire regimes by Aboriginal landscape burning and megafaunal extinction, a finding that probably also applies to other fire-prone vegetation across Australia.