House mice (Mus musculus) arrived in the Americas only recently in association with European colonization (~400–600 generations), but have spread rapidly and show evidence of local adaptation. Here, we take advantage of this genetic model system to investigate the genomic basis of environmental adaptation in house mice. First, we documented clinal patterns of phenotypic variation in 50 wild-caught mice from a latitudinal transect in Eastern North America. Next, we found that progeny of mice from different latitudes, raised in a common laboratory environment, displayed differences in a number of complex traits related to fitness. Consistent with Bergmann’s rule, mice from higher latitudes were larger and fatter than mice from lower latitudes. They also built bigger nests and differed in aspects of blood chemistry related to metabolism. Then, combining exomic, genomic, and transcriptomic data, we identified specific candidate genes underlying adaptive variation. In particular, we defined a short list of genes with cis-eQTL that were identified as candidates in exomic and genomic analyses, all of which have known ties to phenotypes that vary among the studied populations. Thus, wild mice and the newly developed strains represent a valuable resource for future study of the links between genetic variation, phenotypic variation, and climate.