While a growing body of evidence indicates that North Atlantic millennial-scale climate variability extends to the Early Pleistocene, its impact on terrestrial ecosystems has not been established. Here we present ultra-high resolution (70–140 year) joint foraminiferal isotopic and pollen analyses from IODP Site U1385 off Portugal, focusing on a short glacial section of Marine Isotope Stage 38, ~ 1.26 million years ago. Our records reveal the presence of millennial-scale variability in the coupled ocean–atmosphere-land system in the North Atlantic and provide the first direct evidence for the response of western Iberian vegetation to abrupt climate changes in the Early Pleistocene. The magnitude and pacing of changes bear significant similarities to Dansgaard-Oeschger variability of the Late/Middle Pleistocene.