Growth in arctic vegetation is generally expected to increase under a warming climate, particularly among deciduous shrubs. We analyzed annual ring growth for an abundant and nearly circumpolar erect willow (Salix lanata L.) from the coastal zone of the northwest Russian Arctic (Nenets Autonomous Okrug). The resulting chronology is strongly related to summer temperature for the period 1942–2005. Remarkably high correlations occur at long distances (>1600 km) across the tundra and taiga zones of West Siberia and Eastern Europe. We also found a clear relationship with photosynthetic activity for upland vegetation at a regional scale for the period 1981–2005, confirming a parallel ‘greening’ trend reported for similarly warming North American portions of the tundra biome. The standardized growth curve suggests a significant increase in shrub willow growth over the last six decades. These findings are in line with field and remote sensing studies that have assigned a strong shrub component to the reported greening signal since the early 1980s. Furthermore, the growth trend agrees with qualitative observations by nomadic Nenets reindeer herders of recent increases in willow size in the region. The quality of the chronology as a climate proxy is exceptional. Given its wide geographic distribution and the ready preservation of wood in permafrost, S. lanata L. has great potential for extended temperature reconstructions in remote areas across the Arctic.