Understanding both the role of selection in driving phenotypic change and its underlying genetic basis remain major challenges in evolutionary biology. Here, we use modern tools to revisit a classic system of local adaptation in the North American deer mouse, Peromyscus maniculatus, which occupies two main habitat types: prairie and forest. Using historical collections, we find that forest-dwelling mice have longer tails than those from nonforested habitat, even when we account for individual and population relatedness. Using genome-wide SNP data, we show that mice from forested habitats in the eastern and western parts of their range form separate clades, suggesting that increased tail length evolved independently. We find that forest mice in the east and west have both more and longer caudal vertebrae, but not trunk vertebrae, than nearby prairie forms. By intercrossing prairie and forest mice, we show that the number and length of caudal vertebrae are not correlated in this recombinant population, indicating that variation in these traits is controlled by separate genetic loci. Together, these results demonstrate convergent evolution of the long-tailed forest phenotype through two distinct genetic mechanisms, affecting number and length of vertebrae, and suggest that these morphological changes—either independently or together—are adaptive.