During the Soviet Virgin Lands Campaign, approximately 23 million hectares (Mha) of Eurasian steppe grassland were converted into cropland in Northern Kazakhstan from 1954 to 1963. As a result Kazakhstan became an important breadbasket of the former Soviet Union. However, the collapse of the Soviet Union in 1991 triggered widespread agricultural abandonment, and much cropland reverted to grasslands. Our goal in this study was to reconstruct and analyze agricultural land-cover change since the eve of the Virgin Lands Campaign, from 1953 to 2010 in Kostanay Province, a region that is representative of Northern Kazakhstan. Further, we assessed the potential of currently idle cropland for re-cultivation. We reconstructed the cropland extent before and after the Virgin Lands Campaign using archival maps, and we mapped the agricultural land cover in the late Soviet and post-Soviet period using multi-seasonal Landsat TM/ETM+ images from circa 1990, 2000 and 2010. Cropland extent peaked at approximately 3.1 Mha in our study area in 1990, 38% of which had been converted from grasslands from 1954 to 1961. After the collapse of the Soviet Union, 45% of the Soviet cropland was abandoned and had reverted to grassland by 2000. After 2000, cropland contraction and re-cultivation were balanced. Using spatial logistic regressions we found that cropland expansion during the Virgin Lands Campaign was significantly associated with favorable agro-environmental conditions. In contrast, cropland expansion after the Campaign until 1990, as well as cropland contraction after 1990, occurred mainly in areas that were less favorable for agriculture. Cropland re-cultivation after 2000 was occurring on lands with relatively favorable agro-environmental conditions in comparison to remaining idle croplands, albeit with much lower agro-environmental endowment compared to stable croplands from 1990 to 2010. In sum, we found that cropland production potentials of the currently uncultivated areas are much lower than commonly believed, and further cropland expansion is only possible at the expense of marginal lands. Our results suggest if increasing production is a goal, improving crop yields in currently cultivated lands should be a focus, whereas extensive livestock grazing as well as the conservation of non-provisioning ecosystem services and biodiversity should be priority on more marginal lands.