Background: The carbon stored in vegetation varies across tropical landscapes due to a complex mix of climatic and edaphic variables, as well as direct human interventions such as deforestation and forest degradation. Mapping and monitoring this variation is essential if policy developments such as REDD+ (Reducing Emissions from Deforestation and Forest Degradation) are to be known to have succeeded or failed. Results: We produce a map of carbon storage across the watershed of the Tanzanian Eastern Arc Mountains (33.9 million ha) using 1,611 forest inventory plots, and correlations with associated climate, soil and disturbance data. As expected, tropical forest stores more carbon per hectare (182 Mg C ha-1) than woody savanna (51 Mg C ha-1). However, woody savanna is the largest aggregate carbon store, with 0.49 Pg C over 9.6 million ha. We estimate the whole landscape stores 1.3 Pg C, significantly higher than most previous estimates for the region. The 95% Confidence Interval for this method (0.9 to 3.2 Pg C) is larger than simpler look-up table methods (1.5 to 1.6 Pg C), suggesting simpler methods may underestimate uncertainty. Using a small number of inventory plots with two censuses (n = 43) to assess changes in carbon storage, and applying the same mapping procedures, we found that carbon storage in the tree-dominated ecosystems has decreased, th