The widespread extinctions of large mammals at the end of the Pleistocene epoch have often been attributed to the depredations of humans; here we present genetic evidence that questions this assumption. We used ancient DNA and Bayesian techniques to reconstruct a detailed genetic history of bison throughout the late Pleistocene and Holocene epochs. Our analyses depict a large diverse population living throughout Beringia until around 37,000 years before the present, when the population's genetic diversity began to decline dramatically. The timing of this decline correlates with environmental changes associated with the onset of the last glacial cycle, whereas archaeological evidence does not support the presence of large populations of humans in Eastern Beringia until more than 15,000 years later.