Agulhas leakage brings warn and salty waters from the Indian Ocean into the South Atlantic, which can potentially affect the stability of the Atlantic Meridional Overturning Circulation and consequently climate. We use an ocean eddy-resolving coupled climate model, the Community Climate System Model (CCSM4), to study the variability of Agulhas leakage in the presence of full air-sea coupling. An Agulhas leakage time-series is constructed by applying off-line Lagrangian particle tracking and we show that standard-monthly outputs capture 80% of Agulhas leakage variability on time scales longer than a month when compared to five-daily outputs. In a control simulation with fixed 1990 CO2 levels, we find that the Southern Hemisphere westerlies relate differently to Agulhas leakage on different time scales, leakage events at sub-annual timescales correspond to an equatorward shift of the westerly jet, while on longer time scales increased leakage is linked to a strengthening of the westerlies. The former is surprising, since it contradicts pale- oceanographic observations that suggest an expanding gap between the African continent and westerly jet has accompanied enhanced Agulhas leakage in the past. We explore the physical mechanisms behind these correlations, including the role of stochastic atmospheric forcing and air-sea coupling.