Since the 1960s, large-scale deforestation in the Amazon Basin has contributed to rising global CO2 concentrations and to climate change. Recent advances in satellite observations enable estimates of gross losses of above-ground biomass (AGB) stocks due to deforestation. However, because of simultaneous regrowth, the net contribution of deforestation emissions to rising atmospheric CO2 concentrations is poorly quantified. Climate change may also reduce the potential for forest regeneration in previously disturbed regions. Here, we address these points of uncertainty with a machine-learning approach that combines satellite observations of AGB with climate data across the Amazon Basin to reconstruct annual maps of potential AGB during 1993-2012, the above-ground C storage potential of the undisturbed landscape. We derive a 2.2 Pg C loss of AGB over the study period, and, for the regions where these losses occur, we estimate a 0.7 Pg C reduction in potential AGB. Thus, climate change has led to a decline of ~1/3 in the capacity of these disturbed forests to recover and recapture the C lost in disturbances during 1993-2012. Our approach further shows that annual variations in land use change mask the natural relationship between the El Niño/Southern Oscillation and AGB stocks in disturbed regions.