A fundamental issue in the evolution of human culture concerns the route and conditions of anatomically modern hominids during the migration out of Africa. A particular question is, how could anatomically modern hominids cross the hyperarid Arabian deserts? Here we outline the evidence for significant presence of freshwater along the Red Sea shores during the last interglacial period. Freshwater caused an extensive recrystallization of coral reefs from aragonite to calcite, indicating uplift of the reefs through well-developed phreatic freshwater coastal aquifers. Applying novel open-system U-Th dating methodology to the calcitic corals, we dated the freshwater recrystallization to ca. 140 ka, consistent with other geological lines of evidence placing the migration of anatomically modern hominids out of Africa at the onset of the last interglacial.