Although it is generally agreed that the Arctic flora is among the youngest and least diverse on Earth, the processes that shaped it are poorly understood. Here we present 50 thousand years (kyr) of Arctic vegetation history, derived from the first large-scale ancient DNA metabarcoding study of circumpolar plant diversity. For this interval we also explore nematode diversity as a proxy for modelling vegetation cover and soil quality, and diets of herbivorous megafaunal mammals, many of which became extinct around 10 kyr bp (before present). For much of the period investigated, Arctic vegetation consisted of dry steppe-tundra dominated by forbs (non-graminoid herbaceous vascular plants). During the Last Glacial Maximum (25–15 kyr bp), diversity declined markedly, although forbs remained dominant. Much changed after 10 kyr bp, with the appearance of moist tundra dominated by woody plants and graminoids. Our analyses indicate that both graminoids and forbs would have featured in megafaunal diets. As such, our findings question the predominance of a Late Quaternary graminoid-dominated Arctic mammoth steppe.