Atmospheric model simulations with different extents of sea-ice are compared with reconstructed European mean annual temperatures derived from permafrost indicators. Analysis of the results suggest that during cold phases of the Last Glacial, the southern margin of permafrost in western Europe was controlled by the latitude of the winter sea-ice margin in the North Atlantic Ocean. In this case reconstructions of permafrost extent in Europe may be used to constrain past winter sea-ice conditions in the North Atlantic Ocean. Accordingly, extensive North Atlantic sea-ice cover southwards to at least 50°N is inferred during four phases of the Last Glaciation: (1) Early Pleniglacial (74-59 cal kyr BP), (2) the Hasselo Stadial (41.5-40 cal kyr BP), (3) the LGM (23-19 cal kyr BP) and (4) the Younger Dryas (12.7-11.5 cal kyr BP). The extensive sea-ice cover for the phase of maximum cold disagrees with recent studies suggesting a relatively warm North Atlantic during the LGM, while it agrees with the original CLIMAP reconstruction. Moreover, the estimate for the Younger Dryas cooling conflicts with reconstructions based on marine proxy data. © 2002 Elsevier Science Ltd. All rights reserved.