Lions were the most widespread carnivores in the late Pleistocene, ranging from southern Africa to the southern USA, but little is known about the evolutionary relationships among these Pleistocene populations or the dynamics that led to their extinction. Using ancient DNA techniques, we obtained mitochondrial sequences from 52 individuals sampled across the present and former range of lions. Phylogenetic analysis revealed three distinct clusters: (i) modern lions, Panthera leo; (ii) extinct Pleistocene cave lions, which formed a homogeneous population extending from Europe across Beringia (Siberia, Alaska and western Canada); and (iii) extinct American lions, which formed a separate population south of the Pleistocene ice sheets. The American lion appears to have become genetically isolated around 340 000 years ago, despite the apparent lack of significant barriers to gene flow with Beringian populations through much of the late Pleistocene. We found potential evidence of a severe population bottleneck in the cave lion during the previous interstadial, sometime after 48 000 years, adding to evidence from bison, mammoths, horses and brown bears that megafaunal populations underwent major genetic alterations throughout the last interstadial, potentially presaging the processes involved in the subsequent end-Pleistocene mass extinctions.