In order to specify potentially causal relationships between climate, permafrost extent and sea-ice cover we apply a twofold research strategy: (1) we cover a large range of climate conditions varying from full glacial to the relatively warm climate projected for the end of the 21st Century, (2) we combine new proxy-based reconstructions of Eurasian permafrost extent during the LGM and climate model simulations. We find that that there is a linear relationship between the winter sea-ice extent in the North Atlantic and Arctic Oceans and the latitude of the southernmost permafrost limit in Eurasia. During the LGM, extensive sea-ice cover caused a zonal permafrost distribution with the southern margin extending W-E and reaching 47°N, contrasting with the present-day NW-SE trending margin (66°-52°N). We infer that under global warming scenarios projected by climate models for the 21st Century the Arctic sea-ice cover decline will cause widespread instability of, mainly discontinuous, permafrost in Eurasian lowlands. © 2011 Elsevier Ltd.