Pollen, stomata, and macrofossils in a lake core with a basal date of 9700 14C BP were used to reconstruct past changes in climate and vegetation in the arctic tree line area, northeast European Russia. A palsa peat profile was investigated to establish a chronology of mire initiation and permafrost development during the Holocene. Macrofossils show that tree birch was present in the study area at the beginning of the Holocene and stands of spruce became established shortly thereafter. However, pollen evidence suggests that almost 400 years passed before the area was occupied by a mixed spruce–birch forest, which lasted until ca. 5000 BP. Subsequently, the area reverted to forest–tundra. Paludification began ca. 9000 BP continuing at least until 5700 BP. The conditions were permafrost-free at least until 4500 BP. The latest permafrost aggradation phase is dated to the Little Ice Age. We interpret summer temperatures to have been ca. 3–4 °C higher between ca. 8900 and 5500 BP than at present, and the lowest temperature regime of the Holocene to have occurred between 2700 and 2100 BP.