The nature and tempo of Holocene climate variability is examined in the record of forest vegetation from western Mediterranean marine core MD95-2043. Episodes of forest decline occurred at 10.1, 9.2, 8.3, 7.4, 5.4–4.5 and 3.7–2.9 cal. ka BP, and between 1.9 cal. ka BP and the top of the record (1.3 cal. ka BP). Wavelet analysis confirms a ~900 yr periodicity prior to and during the early Holocene and the dominance of a ~1750 yr periodicity after 6 cal. ka BP. The ~900 yr periodicity has counterparts in numerous North Atlantic and Northern Hemisphere palaeoclimate records, and in solar irradiance proxies (Δ¹⁴C and ¹⁰Be), and may relate to a Sun–climate connection during the early Holocene. Comparisons between the MD95-2043 forest record and strategically located records from Morocco, Iceland, Norway and Israel suggest that the ~1750 yr mid- to late-Holocene oscillation reflects shifts between a prevailing strong and weak state of the zonal flow, with impacts similar to the positive and negative modes of the present-day North Atlantic Oscillation (NAO). The mid- to late-Holocene millennial oscillation in zonal flow appears closely coupled to North Atlantic surface ocean circulation dynamics, and may have been driven by an internal oscillation in deep-water convection strength. The findings suggest that the mid-Holocene transition in western Mediterranean climate was accompanied by a shift in the fundamental tempo of millennial-scale variability, reflecting contrasting sensitivity of the North Atlantic climate system to different forcing factors (solar versus oceanic) under deglacial and fully interglacial conditions.