North Atlantic climate during the last glacial period was marked by instability that included large swings in temperature on millennial time scales. Less is known about the existence of such variability during older glacial periods of the Pleistocene when orbital and glacial boundary conditions differed from the last glaciation. I reconstructed millennial changes in surface and deep-water properties at Site U1385 (the “Shackleton site”) on the Iberian Margin for the last 1.5 million years, which includes the Middle Pleistocene Transition (MPT). The results demonstrate that millennial variability was a persistent feature of intermediate glacial states, and exhibits strong threshold behaviour that is symptomatic of a non-linear system. The main change across the MPT is that in the 41-kyr world, millennial variability lasted throughout the entire glacial period, whereas afterwards it is focused mainly on the transitions into and out of glacial states (i.e., inceptions and terminations). Millennial variability in sea ice and thermohaline circulation may be an important mechanism for linking internal climate dynamics with external astronomical forcing by regulating carbon storage in the deep-sea and atmospheric CO2 levels.