Two isotopic ice core records from western Svalbard are calibrated to reconstruct more than 1000 years of past winter surface air temperature variations in Longyearbyen, Svalbard, and Vardo, northern Norway. Analysis of the derived reconstructions suggests that the climate evolution of the last millennium in these study areas comprises three major sub-periods. The cooling stage in Svalbard (ca. 800-1800) is characterized by a progressive winter cooling of approximately 0.9 degrees C century(-1) (0.38 degrees C century(-1) for Vardo) and a lack of distinct signs of abrupt climate transitions. This makes it difficult to associate the onset of the Little Ice Age in Svalbard with any particular time period. During the 1800s, which according to our results was the coldest century in Svalbard, the winter cooling associated with the Little Ice Age was on the order of 4 degrees C (1.3 degrees C for Vardo) compared to the 1900s. The rapid warming that commenced at the beginning of the 20th century was accompanied by a parallel decline in sea-ice extent in the study area. However, both the reconstructed winter temperatures as well as indirect indicators of summer temperatures suggest the Medieval period before the 1200s was at least as warm as at the end of the 1990s in Svalbard.