Arctic tundra currently stores half of the global soil carbon (C) stock(1). Climate warming in the Arctic may lead to accelerated CO2 release through enhanced decomposition and turn Arctic ecosystems from a net C sink into a net C source, if warming enhances decomposition more than plant photosynthesis(2). A large portion of the circumpolar Arctic is grazed by reindeer/caribou, and grazing causes important vegetation shifts in the long-term. Using a unique experimental set-up, where areas experiencing more than 50 years of either light (LG) or heavy (HG) grazing were warmed and/or fertilized, we show that under ambient conditions areas under LG were a 70% stronger C sink than HG areas. Although warming decreased the C sink by 38% under LG, it had no effect under HG. Grazing history will thus be an important determinant in the response of ecosystem C balance to climate warming, which at present is not taken into account in climate change models.