An earlier study revealed the strong phylogeographical structure of the lesser white-toothed shrew (Crocidura suaveolens group) within the northern Palaearctic. Here, we aim to reconstruct the colonization history of Mediterranean islands and to clarify the biogeography and phylogeographical relationships of the poorly documented Middle East region with the northern Palaearctic. We performed analyses on 998-bp-long haplotypes of the mitochondrial cytochrome b gene of 143 samples collected around the Mediterranean basin, including islands and the Middle East. The analyses suggest that the Cypriot shrew belongs to the rare group of relict insular Pleistocene mammal taxa that have survived to the present day. In contrast, the Cretan, Corsican and Menorcan populations were independently introduced from the Middle East during the Holocene. The phylogeographical structure of this temperate Palaearctic species within the Middle East appears to be complex and rich in diversity, probably reflecting fragmentation of the area by numerous mountain chains. Four deeply divergent clades of the C. suaveolens group occur in the area, meaning that a hypothetical contact zone remains to be located in central western Iran.