It is commonly believed that trees were absent in Scandinavia during the last glaciation and first recolonized the Scandinavian Peninsula with the retreat of its ice sheet some 9000 years ago. Here, we show the presence of a rare mitochondrial DNA haplotype of spruce that appears unique to Scandinavia and with its highest frequency to the west-an area believed to sustain ice-free refugia during most of the last ice age. We further show the survival of DNA from this haplotype in lake sediments and pollen of Trøndelag in central Norway dating back ~10,300 years and chloroplast DNA of pine and spruce in lake sediments adjacent to the ice-free Andøya refugium in northwestern Norway as early as ~22,000 and 17,700 years ago, respectively. Our findings imply that conifer trees survived in ice-free refugia of Scandinavia during the last glaciation, challenging current views on survival and spread of trees as a response to climate changes.