A recent update of the PALEOFAUNA database (including new 14C dates) revealed new insights in the changes in the geographical distribution and the (local) extinction of larger mammals in Northern Eurasia during the second part of the Late Pleistocene and the Holocene, a period with dramatic changes in climate. In this paper, we present and discuss the observed changes in the distribution of two herbivore species: the musk ox Ovibos moschatus and the extinct bison Bison priscus, which are the major components of the “mammoth steppe” mammalian assemblage. The decrease of their ranges and their extinction during the Holocene (as a part of the Megafauna extinction in Eurasia) was primarily connected with changes in climate and partly the result of Anthropogenic pressure.