The long-distance movements made by humans through history are quickly erased by time but can be reconstructed by studying the genetic make-up of organisms that travelled with them. The phylogeography of the western house mouse (Mus musculus domesticus), whose current widespread distribution around the world has been caused directly by the movements of (primarily) European people, has proved particularly informative in a series of recent studies. The geographic distributions of genetic lineages in this commensal have been linked to the Iron Age movements within the Mediterranean region and Western Europe, the extensive maritime activities of the Vikings in the 9th to 11th centuries, and the colonisation of distant landmasses and islands by the Western European nations starting in the 15th century. We review here recent insights into human history based on phylogeographic studies of mice and other species that have travelled with humans, and discuss how emerging genomic methodologies will increase the precision of these inferences.