Humans have introduced many species onto remote oceanic islands. The house mouse (Mus musculus) is a human commensal and has consequently been transported to oceanic islands around the globe as an accidental stowaway. The history of these introductions can tell us not only about the mice themselves but also about the people that transported them. Following a phylogeographic approach, we used mitochondrial D-loop sequence variation (within an 849- to 864-bp fragment) to study house mouse colonization of the Azores. A total of 239 sequences were obtained from all nine islands, and interpretation was helped by previously published Iberian sequences and 66 newly generated Spanish sequences. A Bayesian analysis revealed presence in the Azores of most of the D-loop clades previously described in the domesticus subspecies of the house mouse, suggesting a complex colonization history of the archipelago as a whole from multiple geographical origins, but much less heterogeneity (often single colonization?) within islands. The expected historical link with mainland Portugal was reflected in the pattern of D-loop variation of some of the islands but not all. A more unexpected association with a distant North European source area was also detected in three islands, possibly reflecting human contact with the Azores prior to the 15th century discovery by Portuguese mariners. Widening the scope to colonization of the Macaronesian islands as a whole, human linkages between the Azores, Madeira, the Canaries, Portugal and Spain were revealed through the sharing of mouse sequences between these areas. From these and other data, we suggest mouse studies may help resolve historical uncertainties relating to the ‘Age of Discovery’.