The magnitude of heat and salt transfer between the Indian and Atlantic oceans through 'Agulhas leakage' is considered important for balancing the global thermohaline circulation. Increases or reductions of this leakage lead to strengthening or weakening of the Atlantic meridional overturning and associated variation of North Atlantic Deep Water formation. Here we show that modern Agulhas waters, which migrate into the south Atlantic Ocean in the form of an Agulhas ring, contain a characteristic assemblage of planktic foraminifera. We use this assemblage as a modern analogue to investigate the Agulhas leakage history over the past 550,000 years from a sediment record in the Cape basin. Our reconstruction indicates that Indian-Atlantic water exchange was highly variable: enhanced during present and past interglacials and largely reduced during glacial intervals. Coherent variability of Agulhas leakage with northern summer insolation suggests a teleconnection to the monsoon system. The onset of increased Agulhas leakage during late glacial conditions took place when glacial ice volume was maximal, suggesting a crucial role for Agulhas leakage in glacial terminations, timing of interhemispheric climate change and the resulting resumption of the Atlantic meridional overturning circulation.