Antarctic sea ice has paradoxically become more extensive over the past four decades despite a warming climate. The regional expression of this trend has been linked to changes in vertical redistribution of ocean heat and large-scale wind-field shifts. However, the short length of modern observations has hindered attempts to attribute this trend to anthropogenic forcing or natural variability. Here, we present two new decadal-resolution records of sea ice and sea surface temperatures that document pervasive regional climate heterogeneity in Indian Antarctic sea-ice cover over the last 2,000 years. Data assimilation of our marine records in a climate model suggests that the reconstructed dichotomous regional conditions were driven by the multi-decadal variability of the El Nino Southern Oscillation and Southern Annular Mode (SAM). For example, during an El Nino/SAM- combination, the northward sea-ice transport was reduced while heat advection from the subtropics to the Southern Ocean increased, which resulted in reduced sea-ice extent in the Indian sector as sea ice was compacted along the Antarctic coast. Our results therefore indicate that natural variability is large in the Southern Ocean and suggest that it has played a crucial role in the recent sea-ice trends and their decadal variability in this region.