Reconstructions of ancient atmospheric carbon dioxide (CO2) variations help us better understand how the global carbon cycle and climate are linked. We compared CO2 variations on millennial time scales between 20,000 and 90,000 years ago with an Antarctic temperature proxy and records of abrupt climate change in the Northern Hemisphere. CO2 concentration and Antarctic temperature were positively correlated over millennial-scale climate cycles, implying a strong connection to Southern Ocean processes. Evidence from marine sediment proxies indicates that CO2 concentration rose most rapidly when North Atlantic Deep Water shoaled and stratification in the Southern Ocean was reduced. These increases in CO2 concentration occurred during stadial (cold) periods in the Northern Hemisphere, several thousand years before abrupt warming events in Greenland.