The molecular signatures of the recent expansion of the western house mouse, Mus musculus domesticus, around the Mediterranean basin are investigated through the study of mitochondrial D-loop polymorphism on a 1313 individual dataset. When reducing the complexity of the matrilineal network to a series of haplogroups (HGs), our main results indicate that: (i) several HGs are recognized which seem to have almost simultaneously diverged from each other, confirming a recent expansion for the whole subspecies; (ii) some HGs are geographically delimited while others are widespread, indicative of multiple introductions or secondary exchanges; (iii) mice from the western and the eastern coasts of Africa harbour largely different sets of HGs; and (iv) HGs from the two shores of the Mediterranean are more similar in the west than in the east. This pattern is in keeping with the two-step westward expansion proposed by zooarchaeological data, an early one coincident with the Neolithic progression and limited to the eastern Mediterranean and a later one, particularly evident in the western Mediterranean, related to the generalization of maritime trade during the first millennium BC and onwards. The dispersal of mice along with humans, which continues until today, has for instance left complex footprints on the long ago colonized Cyprus or more simple ones on the much more recently populated Canary Islands.