How organisms respond to environmental change is a long-standing question in evolutionary biology. Species invading novel habitats provide an opportunity to examine contemporary evolution in action, and decipher the pace of evolutionary change over short time scales. Here we characterized phenotypic evolution in the Italian plethodontid salamander, Hydromantes strinatii following the recent colonization of an artificial cave by a forest floor population. When compared with a nearby and genetically related population in the natural forest floor and a nearby cave population, the artificial cave population displayed significant differences in overall foot shape, with more inter-digital webbing relative to the other populations. Further, this population evolved significantly larger feet, which corresponded more closely to those found in other cave populations than to forest floor populations to which the cave population is closely related. Finally, we quantified the rate of evolution for both foot shape and foot area, and found that both traits displayed large and significant evolutionary rates, at levels corresponding to other classic cases of rapid evolution in vertebrates. Together these findings reveal that the response to novel environmental pressures can be large and rapid, and that the anatomical shifts observed in the artificial cave population of H. strinatii may represent a case of rapid evolution in response to novel environmental pressures.