Understanding both the role of selection in driving phenotypic change and its underlying genetic basis remain major challenges in evolutionary biology. Here we focus on 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 demonstrate that forest-dwelling mice have longer tails than those from non-forested habitats, even when we account for individual and population relatedness. Based on genome-wide SNP capture data, we find that mice from forested habitats in the eastern and western parts of their range form separate clades, suggesting that increased tail length evolved independently from a short-tailed ancestor. Two major changes in skeletal morphology can give rise to longer tails–increased number and increased length of vertebrae–and 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. Using a second-generation intercross between a prairie and forest pair, we show that the number and length of caudal vertebrae are not correlated in this recombinant population, suggesting that variation in these traits is controlled by separate genetic loci. Together, these results demonstrate convergent evolution of the long-tailed forest phenotype through multiple, distinct genetic mechanisms (controlling vertebral length and vertebral number), thus suggesting that these morphological changes–either independently or together–are adaptive.