We present a revised and extended high Arctic air temperature reconstruction from a single proxy that spans the past ~12,000 y (up to 2009 CE). Our reconstruction from the Agassiz ice cap (Ellesmere Island, Canada) indicates an earlier and warmer Holocene thermal maximum with early Holocene temperatures that are 4-5 °C warmer compared with a previous reconstruction, and regularly exceed contemporary values for a period of ~3,000 y. Our results show that air temperatures in this region are now at their warmest in the past 6,800-7,800 y, and that the recent rate of temperature change is unprecedented over the entire Holocene. The warmer early Holocene inferred from the Agassiz ice core leads to an estimated ~1 km of ice thinning in northwest Greenland during the early Holocene using the Camp Century ice core. Ice modeling results show that this large thinning is consistent with our air temperature reconstruction. The modeling results also demonstrate the broader significance of the enhanced warming, with a retreat of the northern ice margin behind its present position in the mid Holocene and a ~25% increase in total Greenland ice sheet mass loss (~1.4 m sea-level equivalent) during the last deglaciation, both of which have implications for interpreting geodetic measurements of land uplift and gravity changes in northern Greenland.