Pollen and lithopedological data were obtained from Upper Paleolithic sites and Upper Pleistocene loess-soil sequences located between the Sea of Azov and the River Donets, and in the foothills of the Crimean Mountains. During the last Middle Pleniglacial interstadial (Upper Vytachiv soil, 30–27 ka), there existed boreal steppe (south-boreal forest-steppe in Crimea). During the Late Pleniglacial, two main phases of loess accumulation occurred, which were separated by the phase of initial pedogenesis. The loess accumulated under subperiglacial xeric steppe (particularly dry at 15–13 ka), and the incipient soils (Dofinivka unit, 18–15 ka) formed under boreal grassland. During the Late Glacial interstadials, there existed boreal and south-boreal forest-steppe with a relatively wet climate (middle Prychernomorsk soil unit, the upper soil 11.8–11.4 ka). During the Younger Dryas, grassland reappeared under a dry and cool climate (10.9–10.5 ka). Paleoclimatic changes demonstrate the same pattern in both studied areas, and they correspond well with Black Sea transgressive-regressive cycles. Regional differences still existed—during all phases, the climate was the mildest in the western foothills of the Crimean Mountains, the coldest in the Donetsk Upland, and the driest near the Sea of Azov.