Northern permafrost soils contain important carbon stocks. Here we report the long-term response of carbon stocks in high Arctic dwarf shrub tundra to short-term, low-level nutrient enrichment. Twenty years after experimental nitrogen addition, carbon stocks in vegetation and organic soil had almost halved. In contrast, where phosphorus was added with nitrogen, carbon storage increased by more than 50%. These responses were explained by changes in the depths of the moss and organic soil layers. Nitrogen apparently stimulated decomposition, reducing carbon stocks, whilst phosphorus and nitrogen co-stimulated moss productivity, increasing organic matter accumulation. The altered structure of moss and soil layers changed soil thermal regimes, which may further influence decomposition of soil carbon. If climate warming increases phosphorus availability, any increases in nitrogen enrichment from soil warming or expanding human activity in the Arctic may result in increased carbon sequestration. Where phosphorus is limiting in tundra areas, however, nitrogen enrichment may result in carbon loss.