Relative to the past 2,000 years, the Arctic region has warmed significantly over the past few decades. However, the evolution of Arctic temperatures during the rest of the Holocene is less clear. Proxy reconstructions, suggest a long-term cooling trend throughout the mid- to late Holocene, whereas climate model simulations show only minor changes or even warming. Here we present a record of the oxygen isotope composition of permafrost ice wedges from the Lena River Delta in the Siberian Arctic. The isotope values, which reflect winter season temperatures, became progressively more enriched over the past 7,000 years, reaching unprecedented levels in the past five decades. This warming trend during the mid- to late Holocene is in opposition to the cooling seen in other proxy records. However, most of these existing proxy records are biased towards summer temperatures. We argue that the opposing trends are related to the seasonally different orbital forcing over this interval. Furthermore, our reconstructed trend as well as the recent maximum are consistent with the greenhouse gas forcing and climate model simulations, thus reconciling differing estimates of Arctic and northern high-latitude temperature evolution during the Holocene.