Forests often rebound from deforestation following industrialization and urbanization, but for many regions our understanding of where and when forest transitions happened, and how they affected carbon budgets remains poor. One such region is Eastern Europe, where political and socio-economic conditions changed drastically over the last three centuries, but forest trends have not yet been analyzed in detail. We present a new assessment of historical forest change in the European part of the former Soviet Union and the legacies of these changes on contemporary carbon stocks. To reconstruct forest area, we homogenized statistics at the provincial level for ad 1700–2010 to identify forest transition years and forest trends. We contrast our reconstruction with the KK11 and HYDE 3.1 land change scenarios, and use all three datasets to drive the LPJ dynamic global vegetation model to calculate carbon stock dynamics. Our results revealed that forest transitions in Eastern Europe occurred predominantly in the early 20th century, substantially later than in Western Europe. We also found marked geographic variation in forest transitions, with some areas characterized by relatively stable or continuously declining forest area. Our data suggest extensive deforestation in European Russia already prior to ad 1700, and even greater deforestation in the 18th and 19th centuries than in the KK11 and HYDE scenarios. Based on our reconstruction, cumulative carbon emissions from deforestation were greater before 1700 (60 Pg C) than thereafter (29 Pg C). Summed over our entire study area, forest transitions led to a modest uptake in carbon over recent decades, with our dataset showing the smallest effect (<5.5 Pg C) and a more heterogeneous pattern of source and sink regions. This suggests substantial sequestration potential in regrowing forests of the region, a trend that may be amplified through ongoing land abandonment, climate change, and CO2 fertilization.