This study addresses the long-standing issue of postglacial immigration of Picea abies (Norway spruce) into Scandinavia. The main methodological focus is on using megafossil tree remains (wood and cones) of spruce and other species retrieved from the treeline ecotone of the Swedish Scandes as a tool for vegetation reconstruction. The core data come from radiocarbon dating of megafossils preserved in the soil underneath clonal groups of Picea abies, formed by rooting of branches that over time give rise to new upright sterns. At high elevations, we found living spruce clones, which in some cases may be part of a continuous clonal series dating back to-the early Holocene (9500 cal. yr BP). The presence of:Picea in the Swedish Scandes at this early stage concurs with previous megafossil inferences. This date, which places the arrival of Picea very soon after regional deglaciation, is several millennia earlier than the arrival date inferred from pollen data. The persistence of some individual Picea clones from the early Holocene thermal optimum to the present implies that permanently open or semi-open spots existed in the high-mountain landscape even during periods when treelines in general were much higher than at present. Initially, Picea clones appear to have existed in a regional no-analogue vegetation matrix of widely scattered pine (Pinus sylvestris), mountain birch (Betula pubescens ssp. czerepanovii), Siberian larch (Larix sibirica) and thermophilic broadleaved deciduous species. In response to subsequent neoglacial cooling, the alpine character of the landscape has been enhanced through a lowered pine treeline and the disappearance of larch and thermophiles. The endurance of spruces, which escaped fire and other calamities, is due to their inherent phenotypic plasticity. Increasing climatic harshness throughout the Holocene conserved them as crippled krummholz, protected from winter stress by almost complete snow coverage. The appearance of Picea abies exclusively in western Scandinavia shortly after the deglaciation could suggest that the species immigrated from "cryptic" ice age refugia much closer to Scandinavia than conventionally thought.