The submerged sill in the Strait of Messina, which is located today at a minimum depth of 81 m below sea level (bsl), represents the only land connection between Sicily and mainland Italy (and thus Europe) during the last lowstand when the sea level locally stood at about 126 m bsl. Today, the sea crossing to Sicily, although it is less than 4 km at the narrowest point, faces hazardous sea conditions, made famous by the myth of Scylla and Charybdis. Through a multidisciplinary research project, we document the timing and mode of emergence of this land connection during the last 40 kyr. The integrated analysis takes into consideration morphobathymetric and lithological data, and relative sea-level change (both isostatic and tectonic), resulting in the hypothesis that a continental land bridge lasted for at least 500 years between 21.5 and 20 cal ka BP. The emergence may have occurred over an even longer time span if one allows for seafloor erosion by marine currents that have lowered the seabed since the Last Glacial Maximum (LGM). Modelling of palaeotidal velocities shows that sea crossings when sea level was lower than present would have faced even stronger and more hazardous sea currents than today, supporting the hypothesis that earliest human entry into Sicily most probably took place on foot during the period when the sill emerged as dry land. This hypothesis is compared with an analysis of Pleistocene vertebrate faunas in Sicily and mainland Italy, including a new radiocarbon date on bone collagen of an Equus hydruntinus specimen from Grotta di San Teodoro (23–21 cal ka BP), the dispersal abilities of the various animal species involved, particularly their swimming abilities, and the Palaeolithic archaeological record, all of which support the hypothesis of a relatively late land-based colonization of Sicily by Homo sapiens.