Changing environmental conditions cause changes in the distributions of phenotypic traits in natural populations. However, determining the mechanisms responsible for these changes—and, in particular, the relative contributions of phenotypic plasticity versus evolutionary responses—is difficult. To our knowledge, no study has yet reported evidence that evolutionary change underlies the most widely reported phenotypic response to climate change: the advancement of breeding times. In a wild population of red deer, average parturition date has advanced by nearly 2 weeks in 4 decades. Here, we quantify the contribution of plastic, demographic, and genetic components to this change. In particular, we quantify the role of direct phenotypic plasticity in response to increasing temperatures and the role of changes in the population structure. Importantly, we show that adaptive evolution likely played a role in the shift towards earlier parturition dates. The observed rate of evolution was consistent with a response to selection and was less likely to be due to genetic drift. Our study provides a rare example of observed rates of genetic change being consistent with theoretical predictions, although the consistency would not have been detected with a solely phenotypic analysis. It also provides, to our knowledge, the first evidence of both evolution and phenotypic plasticity contributing to advances in phenology in a changing climate.