The sediment record from Lake Ohrid (Southwestern Balkans) represents the longest continuous lake archive in Europe, extending back to 1.36 Ma. We reconstruct the vegetation history based on pollen analysis of the DEEP core to reveal changes in vegetation cover and forest diversity during glacial-interglacial (G-IG) cycles and early basin development. The earliest lake phase saw a significantly different composition rich in relict tree taxa and few herbs. Subsequent establishment of a permanent steppic herb association around 1.2 Ma implies a threshold response to changes in moisture availability and temperature and gradual adjustment of the basin morphology. A change in the character of G-IG cycles during the Early-Middle Pleistocene Transition is reflected in the record by reorganization of the vegetation from obliquity- to eccentricity-paced cycles. Based on a quantitative analysis of tree taxa richness, the first large-scale decline in tree diversity occurred around 0.94 Ma. Subsequent variations in tree richness were largely driven by the amplitude and duration of G-IG cycles. Significant tree richness declines occurred in periods with abundant dry herb associations, pointing to aridity affecting tree population survival. Assessment of long-term legacy effects between global climate and regional vegetation change reveals a significant influence of cool interglacial conditions on subsequent glacial vegetation composition and diversity. This effect is contrary to observations at high latitudes, where glacial intensity is known to control subsequent interglacial vegetation, and the evidence demonstrates that the Lake Ohrid catchment functioned as a refugium for both thermophilous and temperate tree species.