Land use is a critical factor in the global carbon cycle, but land-use effects on carbon fluxes are poorly understood in many regions. One such region is Eastern Europe and the former Soviet Union, where land-use intensity decreased substantially after the collapse of socialism, and farmland abandonment and forest expansion have been widespread. Our goal was to examine how land-use trends affected net carbon fluxes in western Ukraine (57000 km2) and to assess the region’s future carbon sequestration potential. Using satellite-based forest disturbance and farmland abandonment rates from 1988 to 2007, historic forest resource statistics, and a carbon bookkeeping model, we reconstructed carbon fluxes from land use in the 20th century and assessed potential future carbon fluxes until 2100 for a range of forest expansion and logging scenarios. Our results suggested that the low-point in forest cover occurred in the 1920s. Forest expansion between 1930 and 1970 turned the region from a carbon source to a sink, despite intensive logging during socialism. The collapse of the Soviet Union created a vast, but currently largely untapped carbon sequestration potential (up to∼150 Tg C in our study region). Future forest expansion will likely maintain or even increase the region’s current sink strength of 1.48 Tg C yr−1. This may offer substantial opportunities for offsetting industrial carbon emissions and for rural development in regions with otherwise diminishing income opportunities. Throughout Eastern Europe and the former Soviet Union, millions of hectares of farmland were abandoned after the collapse of socialism; thus similar reforestation opportunities may exist in other parts of this region.