The East African long rains constitute the main crop‐growing season in the region. Inter‐annual predictability of this season is low in comparison to the short rains, and recent decadal drying contrasts with climate projections of a wetter future (the “East African climate paradox”). Here, we show that long rains rainfall totals are strongly correlated with 700hPa zonal winds across the Congo basin and Gulf of Guinea (r=0.73). Westerly anomalies align with more rainfall, with the same mechanism controlling co‐variability on inter‐annual and decadal timescales. On both timescales wind anomalies are linked to geopotential anomalies over the Sahel and Sahara, and warming there. Rainfall and wind are significantly correlated with the Madden‐Julian Oscillation (MJO) amplitude, and around 18% of the decadal drying can be explained by MJO amplitude variability. This work shows that predictions of East African rainfall across timescales require robust prediction of both zonal winds and MJO activity.