Populations that colonize islands provide unique insights into demography, adaptation, and the spread of invasive species. House mice on the Faroe Islands evolved exceptionally large bodies after colonization, generating interest from biologists since Darwin. To reconstruct the evolutionary history of these mice, we sequenced genomes of population samples from three Faroe Islands (Sandoy, Nolsoy, and Mykines) and Norway as a mainland comparison. Mice from the Faroe Islands are hybrids between the subspecies Mus musculus domesticus and M. m. musculus, with ancestry alternating along the genome. Analyses based on the site frequency spectrum of single nucleotide polymorphisms and the ancestral recombination graph (ARG) indicate that mice arrived on the Faroe Islands on a timescale consistent with transport by Norwegian Vikings, with colonization of Sandoy likely preceding colonization of Nolsoy. Substantial reductions in nucleotide diversity and effective population size associated with colonization suggest that mice on the Faroe Islands evolved large body size during periods of heightened genetic drift. Genomic scans for positive selection uncover windows with unusual site frequency spectra, but this pattern is mostly generated by clusters of singletons in individual mice. Variants showing evidence of selection in both Nolsoy and Sandoy based on the ARG are enriched for genes with neurological functions. Our findings reveal a dynamic evolutionary history for the enigmatic mice from Faroe Island and emphasize the challenges that accompany population genomic inferences in island populations.