In the current study, different geochemical and biological proxies, including pollen, non-pollen palynomorphs, ostracods and molluscs, from an AMS radiocarbon-dated sediment core from Lake Ochaul (54°14′N, 106°28′E; 641 m a.s.l.) are presented and discussed. Ochaul is a fresh-water lake and an archaeological site situated ca. 100 km northwest of Lake Baikal in the upper reaches of the Lena River. The 260-cm-long sedimentary record presented here spans the Lateglacial–Holocene interval, between ca. 13,500 cal yr BP and the present. The reconstructions of the postglacial vegetation and lake system development are discussed along with the regional climate dynamics and the hemispheric-scale environmental changes. During the Allerød interstadial the region around Lake Ochaul was dominated by sparse taiga forests. Cooling during the Younger Dryas led to a more open tundra landscape where trees formed patchy forest stands in climatically favourable environments. This facilitated a rapid spread of forests at the onset of the Early Holocene during which the study region was probably characterized by seasonally dry climate controlled by the interplay of higher insolation, lower global sea levels and remaining ice sheets in the North Atlantic region. After thermal and moisture optimum conditions and a maximum spread of forests during the Middle Holocene, continuous cooling and a trend to more open forests landscapes marked the Late Holocene. These long-term trends were interrupted by several relatively short episodes of change in the vegetation and algal records, which coincide with short-term (centennial-scale) Northern Hemisphere cooling/drying phases. This shows that the regional vegetation reacted sensitively to these climate oscillations. Six AMS radiocarbon dates of bone material of large herbivorous animals from the Ochaul archaeological site located at the northern shore of the lake provide important information about prehistoric hunter-gatherers and indicate that activities at the site took place at ca. 27,780–27,160 cal yr BP (95% probability range) as well as during the Mesolithic (ca. 8850–8450 cal yr BP), Early, Middle and Late Neolithic (between ca. 6840 and 5490 cal yr BP) and the Iron Age (ca. 2120–1930 cal yr BP). Our results demonstrate that despite major environmental transformations following the Last Glacial Maximum, Lake Ochaul and the Malaya Anga River valley remained attractive for large herbivores and for prehistoric hunter-gatherers, even during the Middle Neolithic cultural “hiatus” (ca. 6660–6060 cal yr BP) in Cis-Baikal, as documented by the published archaeological records.