The worldwide extinction of megafauna during the Late Pleistocene and Early Holocene is evident from the fossil record, with dominant theories suggesting a climate, human or combined impact cause. Consequently, two disparate scenarios are possible for the surviving megafauna during this time period - they could have declined due to similar pressures, or increased in population size due to reductions in competition or other biotic pressures. We therefore infer population histories of 139 extant megafauna species using genomic data which reveal population declines in 91% of species throughout the Quaternary period, with larger species experiencing the strongest decreases. Declines become ubiquitous 32-76 kya across all landmasses, a pattern better explained by worldwide Homo sapiens expansion than by changes in climate. We estimate that, in consequence, total megafauna abundance, biomass, and energy turnover decreased by 92-95% over the past 50,000 years, implying major human-driven ecosystem restructuring at a global scale.