Background: House mice (Mus musculus) are commensals of humans and therefore their phylogeography can reflect human colonization and settlement patterns. Previous studies have linked the distribution of house mouse mitochondrial (mt) DNA clades to areas formerly occupied by the Norwegian Vikings in Norway and the British Isles. Norwegian Viking activity also extended further westwards in the North Atlantic with the settlement of Iceland, short-lived colonies in Greenland and a fleeting colony in Newfoundland in 1000 AD. Here we investigate whether house mouse mtDNA sequences reflect human history in these other regions as well. Results: House mice samples from Iceland, whether from archaeological Viking Age material or from modern-day specimens, had an identical mtDNA haplotype to the clade previously linked with Norwegian Vikings. From mtDNA and microsatellite data, the modern-day Icelandic mice also share the low genetic diversity shown by their human hosts on Iceland. Viking Age mice from Greenland had an mtDNA haplotype deriving from the Icelandic haplotype, but the modern-day Greenlandic mice belong to an entirely different mtDNA clade. We found no genetic association between modern Newfoundland mice and the Icelandic/ancient Greenlandic mice (no ancient Newfoundland mice were available). The modern day Icelandic and Newfoundland mice belong to the subspecies M. m. domesticus, the Greenlandic mice to M. m. musculus. Conclusions: In the North Atlantic region, human settlement history over a thousand years is reflected remarkably by the mtDNA phylogeny of house mice. In Iceland, the mtDNA data show the arrival and continuity of the house mouse population to the present day, while in Greenland the data suggest the arrival, subsequent extinction and recolonization of house mice - in both places mirroring the history of the European human host populations. If house mice arrived in Newfoundland with the Viking settlers at all, then, like the humans, their presence was also fleeting and left no genetic trace. The continuity of mtDNA haplotype in Iceland over 1000 years illustrates that mtDNA can retain the signature of the ancestral house mouse founders. We also show that, in terms of genetic variability, house mouse populations may also track their host human populations.