We used mitochondrial cyt b sequences to investigate the phylogenetic relationships of Crocidura russula (sensu lato) populations across the Strait of Gibraltar, western Europe, Maghreb, and the Mediterranean and Atlantic islands. This revealed very low genetic divergence between European and Moroccan populations. The application of a molecular clock previously calibrated for shrews suggested that the separation of European from Moroccan lineages occurred less than 60 000 bp, which is at least 5 million years (Myr) after the reopening of the Strait of Gibraltar. This means that an overwater dispersal event was responsible for the observed phylogeographical structure. In contrast, genetic analyses revealed that Moroccan populations were highly distinct from Tunisian ones. According to the molecular clock, these populations separated about 2.2 million years ago (Ma), a time marked by sharp alternations of dry and humid climates in the Maghreb. The populations of the Mediterranean islands Ibiza, Pantelleria, and Sardinia were founded from Tunisian populations by overwater dispersal. In conclusion, overwater dispersal across the Strait of Gibraltar, probably assisted by humans, is possible for small terrestrial vertebrates. Moreover, as in Europe, Quaternary climatic fluctuations had a major effect on the phylogeographical structure of the Maghreb biota.