The influence of the large-scale ocean circulation on Sahel rainfall is elusive because of the shortness of the observation record. We reconstructed the history of eolian and fluvial sedimentation on the continental slope off Senegal during the past 57,000 years. Our data show that abrupt onsets of arid conditions in the West African Sahel were linked to cold North Atlantic sea surface temperatures during times of reduced meridional overturning circulation associated with Heinrich Stadials. Climate modeling suggests that this drying is induced by a southward shift of the West African monsoon trough in conjunction with an intensification and southward expansion of the midtropospheric African Easterly Jet.