Paleosalinity and terrigenous sediment input changes reconstructed on two sediment cores from the northernmost Red Sea were used to infer hydrological changes at the southern margin of the Mediterranean climate zone during the Holocene. Between approximately 9.25 and 7.25 thousand years ago, about 3ppm reduced surface water salinities and enhanced fluvial sediment input suggest substantially higher rainfall and freshwater runoff, which thereafter decreased to modern values. The northern Red Sea humid interval is best explained by enhancement and southward extension of rainfall from Mediterranean sources, possibly involving strengthened early Holocene Arctic Oscillation patterns and a regional monsoon-type circulation induced by increased land-sea temperature contrasts. We conclude that Afro-Asian monsoonal rains did not cross the subtropical desert zone during the early to mid-Holocene.