Between the foundation of Constantinople as capital of the eastern half of the Roman Empire in 330 CE and its sack by the Fourth Crusade in 1204 CE, the Byzantine Empire underwent a full cycle from political-economic stability, through rural insecurity and agrarian decline, and back to renewed prosperity. These stages plausibly correspond to the phases of over-extension (K), subsequent release (Ω) and recovery (α) of the Adaptive Cycle in Socio-Ecological Systems. Here we track and partly quantify the consequences of those changes in different regions of Anatolia, firstly for rural settlement (via regional archaeological surveys) and secondly for land cover (via pollen analysis). We also examine the impact of climate changes on the agrarian system. While individual histories vary, the archaeological record shows a major demographic decline between ca .650 and ca. 900 CE in central and southwestern Anatolia, which was then a frontier zone between Byzantine and Arab armies. In these regions, and also in northwest Anatolia, century-scale trends in pollen indicate a substantial decline in the production of cereal and tree crops, and a smaller decline in pastoral activity. During the subsequent recovery (α) phase after 900 CE there was strong regional differentiation, with central Anatolia moving to a new economic system based on agro-pastoralism, while lowland areas of northern and western Anatolia returned to the cultivation of commercial crops such as olive trees. The extent of recovery in the agrarian economy was broadly predictable by the magnitude of its preceding decline, but the trajectories of recovery varied between different regions.