The history of sea level within the Red Sea basin impinges on several areas of research. For archaeology and prehistory, past sea levels of the southern sector define possible pathways of human dispersal out of Africa. For tectonics, the interglacial sea levels provide estimates of rates for vertical tectonics. For global sea level studies, the Red Sea sediments contain a significant record of changing water chemistry with implications on the mass exchange between oceans and ice sheets during glacial cycles. And, because of its geometry and location, the Red Sea provides a test laboratory for models of glacio-hydro-isostasy. The Red Sea margins contain incomplete records of sea level for the Late Holocene, for the Last Glacial Maximum, for the Last Interglacial and for earlier interglacials. These are usually interpreted in terms of tectonics and ocean volume changes but it is shown here that the glacio-hydro-isostatic process is an additional important component with characteristic spatial variability. Through an iterative analysis of the Holocene and interglacial evidence a separation of the tectonic, isostatic and eustatic contributions is possible and we present a predictive model for palaeo-shorelines and water depths for a time interval encompassing the period proposed for migrations of modern humans out of Africa. Principal conclusions include the following. (i) Late Holocene sea level signals evolve along the length of the Red Sea, with characteristic mid-Holocene highstands not developing in the central part. (ii) Last Interglacial sea level signals are also location dependent and, in the absence of tectonics, are not predicted to occur more than 1-2. m above present sea level. (iii) For both periods, Red Sea levels at 'expected far-field' elevations are not necessarily indicative of tectonic stability and the evidence points to a long-wavelength tectonic uplift component along both the African and Arabian northern and central sides of the Red Sea. (iv) The observational evidence is consistent with tectonic and isostatic processes both operating over the past 300,000 years without requiring changes in the time averaged (over a few thousand years) tectonic rates. (v) Recent bathymetric data for the Bab al Mandab region have been compiled to confirm the location and depth of the sill controlling flow in and out of the Red Sea. Throughout the last 400,000 years the Red Sea has remained open to the Gulf of Aden with cross sectional areas at times of glacial maxima about 2% of that today. (vi) The minimum channel widths connecting the Red Sea to the Gulf of Aden at times of lowstand occur south of the Hanish Sill. The channels are less than 4. km wide and remain narrow for as long as local sea levels are below -50. m. This occurs for a number of sustained periods during the last two glacial cycles and earlier. (vii) Periods suitable for crossing between Africa and Arabia without requiring seaworthy boats or seafaring skills occurred periodically throughout the Pleistocene, particularly at times of favourable environmental climatic conditions that occurred during times of sea level lowstand.