Parallel changes in genotype and phenotype in response to similar selection pressures in different populations provide compelling evidence of adaptation. House mice (Mus musculus domesticus) have recently colonized North America and are found in a wide range of environments. Here we measure phenotypic and genotypic differentiation among house mice from five populations sampled across 21° of latitude in western North America, and we compare our results to a parallel latitudinal cline in eastern North America. First, we show that mice are genetically differentiated between transects, indicating that they have independently colonized similar environments in eastern and western North America. Next, we find genetically-based differences in body weight and nest building behavior between mice from the ends of the western transect which mirror differences seen in the eastern transect, demonstrating parallel phenotypic change. We then conduct genome-wide scans for selection and a genome-wide association study to identify targets of selection and candidate genes for body weight. We find some genomic signatures that are unique to each transect, indicating population-specific responses to selection. However, there is significant overlap between genes under selection in eastern and western house mouse transects, providing evidence of parallel genetic evolution in response to similar selection pressures across North America.