To investigate the Holocene climate and treeline dynamics in the European Russian Arctic, we analysed sediment pollen, conifer stomata, and plant macrofossils from Lake Kharinei, a tundra lake near the treeline in the Pechora area. We present quantitative summer temperature reconstructions from Lake Kharinei and Lake Tumbulovaty, a previously studied lake in the same region, using a pollen–climate transfer function based on a new calibration set from northern European Russia. Our records suggest that the early-Holocene summer temperatures from 11,500 cal yr BP onwards were already slightly higher than at present, followed by a stable Holocene Thermal Maximum (HTM) at 8000–3500 cal yr BP when summer temperatures in the tundra were ca. 3°C above present-day values. A Picea forest surrounded Lake Kharinei during the HTM, reaching 150 km north of the present taiga limit. The HTM ended with a temperature drop at 3500–2500 cal yr BP associated with permafrost initiation in the region. Mixed spruce forest began to disappear around Lake Kharinei at ca. 3500 cal yr BP, with the last tree macrofossils recorded at ca. 2500 cal yr BP, suggesting that the present wide tundra zone in the Pechora region formed during the last ca. 3500 yr.