Identifying the genes underlying adaptation is a major challenge in evolutionary biology. Here, we describe the molecular changes underlying adaptive coat color variation in a natural population of rock pocket mice, Chaetodipus intermedius. Rock pocket mice are generally light-colored and live on light-colored rocks. However, populations of dark (melanic) mice are found on dark lava, and this concealing coloration provides protection from avian and mammalian predators. We conducted association studies by using markers in candidate pigmentation genes and discovered four mutations in the melanocortin-1-receptor gene, Mc1r, that seem to be responsible for adaptive melanism in one population of lava-dwelling pocket mice. Interestingly, another melanic population of these mice on a different lava flow shows no association with Mc1r mutations, indicating that adaptive dark color has evolved independently in this species through changes at different genes.