To understand how organisms adapt to novel habitats, which involves both demographic and selective events, we require knowledge of the evolutionary history of populations and also selected alleles. There are still few cases in which the precise mutations (and hence, defined alleles) that contribute to adaptive change have been identified in nature; one exception is the genetic basis of camouflaging pigmentation of oldfield mice (Peromyscus polionotus) that have colonized the sandy dunes of Florida's Gulf Coast. To quantify the genomic impact of colonization as well as the signature of selection, we resequenced 5000 1.5-kb noncoding loci as well as a 160-kb genomic region surrounding the melanocortin-1 receptor (Mc1r), a gene that contributes to pigmentation differences, in beach and mainland populations. Using a genome-wide phylogenetic approach, we recovered a single monophyletic group comprised of beach mice, consistent with a single colonization event of the Gulf Coast. We also found evidence of a severe founder event, estimated to have occurred less than 3000 years ago. In this demographic context, we show that all beach subspecies share a single derived light Mc1r allele, which was likely selected from standing genetic variation that originated in the mainland. Surprisingly, we were unable to identify a clear signature of selection in the Mc1r region, despite independent evidence that this locus contributes to adaptive coloration. Nonetheless, these data allow us to reconstruct and compare the evolutionary history of populations and alleles to better understand how adaptive evolution, following the colonization of a novel habitat, proceeds in nature.