With a range that covered most of northern Eurasia and parts of North America, the cave lion (Panthera spelaea) was one of the most widespread carnivores of the Late Pleistocene. Earlier ancient DNA analyses have shown that it is distinct from modern lions, and have suggested a demographic decline in Beringia during marine isotope stage 3 (MIS 3). Here, we further investigate the Late Pleistocene population dynamics in more detail by combining a powerful algorithm that couples MCMC with coalescent simulations under an approximate Bayesian computation framework. We use an ancient DNA dataset of previously published (n = 34) and new radiocarbon dated specimens (n = 14). Phylogenetic and network analyses based on the mitochondrial control region and the ATP8 gene identified two major haplogroups, one of which appears to vanish around 41,000 cal a BP. The approximate Bayesian computation analysis suggested a decline in effective population size (Ne) in Beringia of at least a 2-fold magnitude that began approximately 47,000 cal a BP, followed by an increase in Ne, most likely around 18,000 cal a BP. The cave lion went through a demographic bottleneck during MIS 3, which may have lasted for several tens of thousands of years, and only recovered shortly before the species' extinction. Several other large mammal species display similar declines in genetic diversity in Beringia during MIS 3, suggesting that major environmental changes might have affected megafaunal populations during this time period.