According to fossil data, the wood mouse arrived in North Africa 7500 ya, while it was present in Europe since Early Pleistocene. Previous molecular studies suggested that its introduction in North Africa probably occurred via the Strait of Gibraltar more than 0.4 Mya ago. In this study, we widely sampled wood mice to get a better understanding of the geographic and demographic history of this species in North Africa and possibly to help resolving the discrepancy between genetic and palaeontological data. Specifically, we wanted to answer the following questions: (1) When and how did the wood mouse arrive in North Africa? and (2) What is its demographic and geographic history in North Africa since its colonization? We collected in the field 438 new individuals and used both mtDNA and six microsatellite markers to answer these questions. Our results confirm that North African wood mice have a south-western European origin and colonized the Maghreb through the Strait of Gibraltar probably during the Mesolithic or slightly after. They first colonized the Tingitana Peninsula and then expanded throughout North Africa. Our genetic data suggest that the ancestral population size comprised numerous individuals reinforcing the idea that wood mice did not colonize Morocco accidentally through rafting of a few individuals, but via recurrent/multiple anthropogenic translocations. No spatial structuring of the genetic variability was recorded in North Africa, from Morocco to Tunisia.