Climate change is rapidly advancing spring phenology [1-3] but at different rates in different species [1, 4]. Whether these advances are solely driven by phenotypic plasticity [2, 5] or also involve evolution is hotly debated (e.g., [5-7]). In some species, including avian long-distance migrants, plastic responses to early springs may be constrained by inherited circannual timing programs [8, 9], making evolutionary adjustment the only viable mechanism for keeping pace with shifting phenology [5, 10]. This constraint may be contributing to population declines in migratory species [5, 10-12]. To test whether a migrant's timing program has evolved [10, 12], we replicated an experimental study of the annual cycle of long-distance migratory pied flycatchers (Ficedula hypoleuca) after 21 years of warming. Flycatchers are a model for studying constrained ecological responses to climate change [6, 10, 12, 13]. We show that the phase of the flycatcher circannual clock controlling spring moult, migration, and reproductive timing advanced by 9 days. A nearby wild population mirrored these changes, concurrently advancing egg-laying by 11 days. Furthermore, the time window during which wild flycatcher reproductive timing was most sensitive to ambient temperature advanced by 0.8 days year(-1). These results support a role of phenotypic evolution  in changing spring phenology [15, 16]. We suggest that the timing programs of long-distance migratory birds may have greater adaptive potential than previously thought, leaving some scope for evolutionary rescue in a changing climate.