The Holocene climate of the Southern Ocean is not well understood, mainly because of the lack of high-resolution reconstructions of ocean surface properties. Here we present a 12,500-yr-long, decadal-scale record of Holocene sea-surface temperatures and sea-ice presence from the Polar Front of the East Atlantic Southern Ocean. The record shows gradual climate change, with no abrupt Neoglacial cooling, and an unprecedented late Holocene warming. The dominant forcing factor appears to be precessional insolation; Northern Hemisphere summer insolation correlates to at least the early to middle Holocene climate trend. Spectral analysis reveals centennial-scale cyclic climate changes with periods of 1220, 1070, 400, and 150 yr. The record shows good correlation to East Antarctic ice cores and to climate records from South Georgia and Bunger Oasis. However, the record shows out-of-phase behavior with regard to climate records from the western Antarctic Peninsula and the Peru-Chile Current; such behavior hints at a climatic divide through Patagonia, the Drake Passage, and between West and East Antarctica.