Reconstructions of the vegetation of Europe during the Last Glacial Maximum (LGM) are an enigma. Pollen-based analyses have suggested that Europe was largely covered by steppe and tundra, and forests persisted only in small refugia. Climate-vegetation model simulations on the other hand have consistently suggested that broad areas of Europe would have been suitable for forest, even in the depths of the last glaciation. Here we reconcile models with data by demonstrating that the highly mobile groups of hunter-gatherers that inhabited Europe at the LGM could have substantially reduced forest cover through the ignition of wildfires. Similar to hunter-gatherers of the more recent past, Upper Paleolithic humans were masters of the use of fire, and preferred inhabiting semi-open landscapes to facilitate foraging, hunting and travel. Incorporating human agency into a dynamic vegetation-fire model and simulating forest cover shows that even small increases in wildfire frequency over natural background levels resulted in large changes in the forested area of Europe, in part because trees were already stressed by low atmospheric CO2 concentrations and the cold, dry, and highly variable climate. Our results suggest that the impact of humans on the glacial landscape of Europe may be one of the earliest large-scale anthropogenic modifications of the earth system.