Large parts of sub-Saharan Africa are experiencing rapid changes in land use and land cover, driven largely by the expansion of small-scale shifting cultivation. This practice creates complex mosaic landscapes with active agricultural fields and patches of mature woodland, interspersed with remnant patches in various stages of regrowth. Our objective here was to examine the rate and extent to which carbon stocks in trees and soils recover after cultivation, and detail how this disturbance and regrowth affect patterns in tree species composition and diversity over 40 years of succession in a miombo woodland landscape in southeast Tanzania. We sampled 67 areas, including plots previously cleared for cultivation, active fields, and mature woodlands for reference purposes. Sites were further stratified by soil texture to test for associated effects. Tree carbon stocks accumulated at an average rate of 0.83 ± 0.10 Mg C x ha(-1) x yr(-1), with soil texture having no clear impact on accumulation rates. Bulk soil carbon stocks on both soil types appeared unaffected by both the initial land clearance and the subsequent regrowth, which resulted in no significant changes over time. Tree species diversity in regrowing plots developed rapidly and within -10 years was equivalent to that of mature woodland. Many of the species found in mature woodlands reappeared relatively quickly after abandonment, although species composition is expected to take considerably longer to recover, with at least 60-80 years required for the compositional similarity between regrowing and mature woodlands to reach levels similar to that among nearby mature woodlands. Through impacts on β-diversity, disturbance was also found to increase the total number of tree species present in the landscape, with many of the recorded species only found in regrowing woodlands. Our results are of relevance to carbon sequestration projects by helping to inform the potential future carbon and biodiversity benefits of restoring disturbed habitats (REDD+). At a time where the use of shifting cultivation is threatened by shifts to larger-scale, commercial agriculture, we show that secondary woodland habitats can retain considerable biodiversity value, and act as carbon sinks.