Climate-proxy records of the past 100,000 years show that the Earth's climate has varied significantly and continuously on timescales as short as a few thousand years [1-7]. Similar variability has also recently been observed for the interval 340-500 thousand years ago . These dramatic climate shifts, expressed most strongly in the North Atlantic region, may be linked to-and possibly amplified by-alterations in the mode of ocean thermohaline circulation [4-9]. Here we use sediment records of past iceberg discharge and deep-water chemistry to show that such millennial-scale oscillations in climate occurred over one million years ago. This was a time of significantly different climate boundary conditions; not only was the early Pleistocene epoch generally warmer, but global climate variations were governed largely by changes in Earth's orbital obliguity. Our results suggest that such millennial-scale climate instability may be a pervasive and long-term characteristic of Earth's climate, rather than just a feature of the strong glacial-interglacial cycles of the past 800,000 years.