The Indian-Atlantic water exchange south of Africa (Agulhas leakage) is a key component of the global ocean circulation. No quantitative estimation of the paleo-Agulhas leakage exists. We quantify the variability in interocean exchange over the past 640,000 years, using planktic foraminiferal assemblage data from two marine sediment records to define an Agulhas leakage efficiency index. We confirm the validity of our new approach with a numerical ocean model that realistically simulates the modern Agulhas leakage changes. Our results suggest that, during the past several glacial-interglacial cycles, the Agulhas leakage varied by ~10 sverdrup and more during major climatic transitions. This lends strong credence to the hypothesis that modifications in the leakage played a key role in changing the overturning circulation to full strength mode. Our results are instrumental for validating and quantifying the contribution of the Indian-Atlantic water leakage to the global climate changes.