Northern and eastern Africa were exposed to significantly wetter conditions relative to present during the early Holocene period known as the African Humid Period (AHP), although the latitudinal extent of the northward expansion of the tropical rain belt remains poorly constrained. New records of Th-normalized accumulation rates in marine sediment cores from the Red Sea and Gulf of Aden are combined with existing records of western Africa dust and terrestrial records across the Sahara Desert, revealing that fluxes of dust transported east from the Sahara decreased by at least 50% during the AHP, due to the development of wetter conditions as far north as ~22°N. These results provide the first quantitative record of sediment and dust accumulation rates in the Red Sea and the Gulf of Aden over the past 20 kyrs and challenge the paradigm of vast vegetative cover across the north and northeastern Sahara Desert during the AHP.