Phenotypic plasticity has been hypothesized to precede and facilitate adaptation to novel environments [1–8], but examples of plasticity preceding adaptation in wild populations are rare (but see [9, 10]). We studied a population of side-blotched lizards, Uta stansburiana, living on a lava flow that formed 22,500 years ago [11] to understand the origin of their novel melanic phenotype that makes them cryptic on the black lava. We found that lizards living on and off of the lava flow exhibited phenotypic plasticity in coloration but also appeared to have heritable differences in pigmentation. We sequenced the exomes of 104 individuals and identified two known regulators of melanin production, PREP and PRKAR1A, which had markedly increased levels of divergence between lizards living on and off the lava flow. The derived variants in PREP and PRKAR1A were only found in the lava population and were associated with increased pigmentation levels in an experimental cohort of hatchling lizards. Simulations suggest that the derived variants in the PREP and PRKAR1A genes arose recently and were under strong positive selection in the lava population. Overall, our results suggest that ancestral plasticity for coloration facilitated initial survival in the lava environment and was followed by genetic changes that modified the phenotype in the direction of the induced plastic response, possibly through de novo mutations. These observations provide a detailed example supporting the hypothesis that plasticity aids in the initial colonization of a novel habitat, with natural selection subsequently refining the phenotype with genetic adaptations to the new environment. Video Abstract: [Figure presented] Plasticity has been hypothesized to precede adaptation to new environments. Corl et al. show that melanic lizards from a lava flow have both ancestral plasticity in coloration and divergence in two genes that increase pigmentation. Plasticity aided in the initial colonization of the new habitat, where natural selection then refined the phenotype.