Concern about the effect of anthropogenic greenhouse gas (GHG) emissions on climate has led to interest in sequestration of carbon in terrestrial sinks, including soils. Industrialized nations with emission reduction commitments under the Kyoto Protocol (Annex I countries) can use soil organic carbon (SOC) sequestration to reduce their GHG emissions. However, a major problem with this mechanism is the high uncertainty of SOC estimates over the large, heterogeneous areas needed to sequester carbon in quantities that are significant relative to CO₂ emissions. A methodology that aims to improve estimates of SOC changes over large areas was developed and tested. The methodology uses Monte Carlo simulation to estimate SOC change over time at multiple locations and assimilates SOC measurements with these estimates using the Ensemble Kalman Filter algorithm (EnKF). The methodology was tested for estimating SOC changes in the farming community of Oumaroubougou, Mali (Latitude: 12.19 °N, Longitude: 5.14 °W). The performance of the methodology was evaluated over a range of specifications for the uncertainty of model parameters and the initial spatial correlation of SOC and model parameters between plots in the experiment. In all cases, EnKF estimates of changes in SOC had lower variances than measurement-based estimates. Specification of the initial spatial correlation of SOC and the model rate parameter, versus assuming no spatial correlation, gave more power to the EnKF when measurements were assimilated. Although further research and testing at larger scales is needed, the methodology appears promising for giving improved estimates of SOC changes with decreased uncertainty.