Tropical ecosystems play a large and complex role in the global carbon cycle. Clearing of natural ecosystems for agriculture leads to large pulses of CO2 to the atmosphere from terrestrial biomass. Concurrently, the remaining intact ecosystems, especially tropical forests, may be sequestering a large amount of carbon from the atmosphere in response to global environmental changes including climate changes and an increase in atmospheric CO2. Here we use an approach that integrates census-based historical land use reconstructions, remote-sensing-based contemporary land use change analyses, and simulation modeling of terrestrial biogeochemistry to estimate the net carbon balance over the period 1901-2006 for the state of Mato Grosso, Brazil, which is one of the most rapidly changing agricultural frontiers in the world. By the end of this period, we estimate that of the state's 925 225 km2, 221 092 km2 have been converted to pastures and 89 533 km2 have been converted to croplands, with forest-to-pasture conversions being the dominant land use trajectory but with recent transitions to croplands increasing rapidly in the last decade. These conversions have led to a cumulative release of 4.8 Pg C to the atmosphere, with 80% from forest clearing and 20% from the clearing of cerrado. Over the same period, we estimate that the residual undisturbed ecosystems accumulated 0.3 Pg C in response to CO2 fertilization. Therefore, the net emissions of carbon from Mato Grosso over this period were 4.5 Pg C. Net carbon emissions from Mato Grosso since 2000 averaged 146 Tg C/yr, on the order of Brazil's fossil fuel emissions during this period. These emissions were associated with the expansion of croplands to grow soybeans. While alternative management regimes in croplands, including tillage, fertilization, and cropping patterns promote carbon storage in ecosystems, they remain a small portion of the net carbon balance for the region. This detailed accounting of a region's carbon balance is the type of foundation analysis needed by the new United Nations Collaborative Programmme for Reducing Emissions from Deforestation and Forest Degradation (REDD).