This article presents an analytical review of the available palaeoenvironmental and archaeological records from the southern part (ca. 42°18′–45°30′N) of Primorye spanning the last ca. 21,000 years. The outlined climate and environmental history of the coastal and continental zones of southern Primorye, based mainly on vegetation reconstructions derived from the study of fossil pollen from sedimentary deposits from various archives, is compared with the archaeological cultural sequence of the region. This shows synchronicity between several phases of climate change and cultural transition, migration and changes in population numbers and/or subsistence strategies. The pronounced warming trend during the Early Holocene (Preboreal and Boreal stages) is associated with increasing numbers of long-term camp sites of the Late Palaeolithic hunter-gatherers and a growing importance of aquatic food resources. The Holocene maximum temperature and moisture conditions during the Atlantic stage were paralleled by the emergence and flourishing of the Neolithic Rudnaya, Vetka and Boisman cultures (ca. 7.7–5.5 14C ka BP/8.5–6.2 cal ka BP). The latter was a specialised maritime forager culture distributed along the Sea of Japan coast, which likely reflects climate conditions and sea water temperatures that promoted a broad spectrum of marine food resources. Towards the end of the Atlantic stage, sea levels decreased and transformed the coastal landscape of southern Primorye, which probably contributed to the decline of the Boisman culture. At the same time, the climate started to become cooler, which is likely related to the eastward migration of Zaisanovskaya culture groups from more continental (cooler) regions to milder southern Primorye. Continuous cooling during the Subboreal was accompanied by further immigrations of Zaisanovskaya people and an increase in millet cultivation, which probably occurred in the region between ca. 4.6–4.1 14C ka BP/5.3–4.6 cal ka BP. With the emergence of the Palaeometal Epoch cultures (ca. 3.6 14C ka BP/4.0 cal ka BP), food production diversified (growing number of cultivated crops, animal husbandry) and intensified, which probably decreased the people's dependence on climatic conditions unfavourable for food procurement. However, the maximum flourishing (ca. 2.8–2.6 14C ka BP/2.9–2.6 cal ka BP) of the Palaeometal Epoch Yankovskaya culture, represented by a maximum number of documented settlement sites in Primorye's prehistoric sequence, was likely related to a coeval short phase of climate amelioration with higher air and sea water temperatures and an increased sea level, which promoted agriculture and a higher productivity of coastal waters.