Understanding the genetic basis of adaptation is a fundamental goal of evolutionary biology. Many of the first examples connecting adaptive phenotypes to specific genetic variants implicated single loci of large effect (e.g., Mc1r in rock pocket mice, Eda in sticklebacks, FRIGIDA in Arabidopsis thaliana). Nevertheless, the majority of adaptive phenotypes are likely to be complex and contingent on interactions between many genes and the environment. Progress in identifying the genetic basis of complex traits has been more limited. The incredibly successful colonization of the Americas by house mice offers a unique opportunity to study environmental adaptation, complex traits, and population genetics in an invasive species that is also the premier mammalian medical model for humans. Despite arriving in the Americas relatively recently with European settlers, the house mouse (Mus musculus domesticus) has expanded into a wide variety of climates and habitats. We sampled five populations of house mice in eastern North America distributed along a latitudinal gradient and established laboratory colonies of mice from the ends of this transect. Using genome and exome scans, gene expression studies, and phenotypic analyses in the field and in the lab, we found strong evidence of environmental adaptation. We identified several phenotypes tied to fitness that differ among the most extreme populations, and those differences persist in the lab over several generations indicating that they have a genetic basis. We also identified specific genes as candidates for environmental adaptation. Importantly, most candidate SNPs are non-coding or synonymous, indicating that regulatory evolution has been key to the success of house mice in varied climates.