Nutrient availability in the arctic is expected to increase in the next century due to accelerated decomposition associated with warming and, to a lesser extent, increased nitrogen deposition. To explore how changes in nutrient availability affect ecosystem carbon (C) cycling, we used radiocarbon to quantify changes in belowground C dynamics associated with long-term fertilization of graminoid-dominated tussock tundra at Toolik Lake, Alaska. Since 1981, yearly fertilization with nitrogen (N) and phosphorus (P) has resulted in a shift to shrub-dominated vegetation. These combined changes have altered the quantity and quality of litter inputs, the vertical distribution and dynamics of fine roots, and the decomposition rate of soil organic C. The loss of C from the deep organic and mineral soil has more than offset the C accumulation in the litter and upper organic soil horizons. In the litter and upper organic horizons, radiocarbon measurements show that increased inputs resulted in overall C accumulation, despite being offset by increased decomposition in some soil pools. To reconcile radiocarbon observations in the deeper organic and mineral soil layers, where most of the ecosystem C loss occurred, both a decrease in input of new root material and a dramatic increase of decomposition rates in centuries-old soil C pools were required. Therefore, with future increases in nutrient availability, we may expect substantial losses of C which took centuries to accumulate.