For decades, arid desert ecosystems in northwest China, covering one-fourth the country's land surface, have experienced a rapid decline in plant species diversity, productivity and soil carbon stock owing to degradation by overgrazing. In this study, plant community composition, diversity and productivity, as well as soil carbon (C) and nitrogen (N) stocks, were monitored over 26Â years from 1981 to 2006 in a severely degraded Haloxylon ammodendron-dominated shrubland where livestock densities were reduced from 4'5 to 1'2 dry sheep equivalent ha-1. The objective was to assess long-term grazing effects on vegetation and soil C and N accumulation dynamics. Results showed that the reduction of grazing pressure significantly increased vegetation cover, plant diversity and productivity, resulting primarily from an increase in livestock-preferred species. Controlled grazing also led to marked increases in soil C and N stocks in the top 30Â cm of soil. This increase was strongly associated with increased plant species richness, vegetation cover and biomass production. Averaged over 26Â years, soil C and N accumulated at rates of 89.9Â g'C and 8.4Â g'N m-2'year-1, respectively, but rates of C and N accumulation varied greatly at different time periods. The greatest species regeneration occurred in the first 8Â years, but the largest C and N accumulation took place during years 9'18, with a time-lag in response to changes in vegetation. Our results provide insights into the long-term recovery patterns of different ecosystem components from the influence of prolonged overgrazing disturbance that cannot be inferred from a short-term study. The findings are important for assessing the resilience of these livestock-disturbed desert ecosystems and developing a more effective strategy for the management of this important biome from a long-term perspective.