North Africa experienced dramatic changes in hydrology and vegetation during the late Quaternary driven by insolation-induced shifts of the tropical rain belt and further modulated by millennial-scale droughts and vegetation-climate feedbacks. While most past proxy and modelling studies concentrated on the temporal and spatial dynamics of the last African humid period, little is known about the intensities and characteristics of pre-Holocene humid periods. Here we present a high-resolution record of fine-grained eastern Saharan dust from the Eastern Mediterranean Sea spanning the last 180 kyr, which is based on the clay mineral composition of the marine sediments, especially the kaolinite/chlorite ratio. Minimum aeolian kaolinite transport occurred during the African Humid Periods because kaolinite deflation was hampered by increased humidity and vegetation cover. Instead, kaolinite weathering from kaolinite-bearing Cenozoic rocks was stored in lake basins, river beds and soils during these periods. During the subsequent dry phases, fine-grained dust was mobilised from the desiccated lakes, rivers and soils resulting in maximum aeolian uptake and transport of kaolinite. The kaolinite transport decreased again when these sediment sources exhausted. We conclude that the amount of clay-sized dust blown out of the Sahara into the Eastern Mediterranean Sea is proportional to the intensity of the kaolinite weathering and accumulation in soils and lake sediments, and thus to the strength of the preceding humid period. These humid periods provided the windows for the migration of modern humans out of Africa, as postulated previously. The strongest humid period occurred during the Eemian and was followed by two weaker phases centred at ca. 100 ka and ca. 80 ka.