Ancient DNA has significantly improved our understanding of the evolution and population history of extinct megafauna. However, few studies have used complete ancient genomes to examine species responses to climate change prior to extinction. The woolly rhinoceros (Coelodonta antiquitatis) was a cold-adapted megaherbivore widely distributed across northern Eurasia during the Late Pleistocene and became extinct approximately 14 thousand years before present (ka BP). While humans and climate change have been proposed as potential causes of extinction [1-3], knowledge is limited on how the woolly rhinoceros was impacted by human arrival and climatic fluctuations [2]. Here, we use one complete nuclear genome and 14 mitogenomes to investigate the demographic history of woolly rhinoceros leading up to its extinction. Unlike other northern megafauna, the effective population size of woolly rhinoceros likely increased at 29.7 ka BP and subsequently remained stable until close to the species’ extinction. Analysis of the nuclear genome from a similar to 18.5-ka-old specimen did not indicate any increased inbreeding or reduced genetic diversity, suggesting that the population size remained steady for more than 13 ka following the arrival of humans [4]. The population contraction leading to extinction of the woolly rhinoceros may have thus been sudden and mostly driven by rapid warming in the Bolling-Allerod interstadial. Furthermore, we identify woolly rhinoceros-specific adaptations to arctic climate, similar to those of the woolly mammoth. This study highlights how species respond differently to climatic fluctuations and further illustrates the potential of palaeogenomics to study the evolutionary history of extinct species.