Climate change has differentially affected the timing of seasonal events for interacting trophic levels, and this has often led to increased selection on seasonal timing. Yet, the environmental variables driving this selection have rarely been identified, limiting our ability to predict future ecological impacts of climate change. Using a dataset spanning 31 years from a natural population of pied flycatchers (Ficedula hypoleuca), we show that directional selection on timing of reproduction intensified in the first two decades (1980–2000) but weakened during the last decade (2001–2010). Against expectation, this pattern could not be explained by the temporal variation in the phenological mismatch with food abundance. We therefore explored an alternative hypothesis that selection on timing was affected by conditions individuals experience when arriving in spring at the breeding grounds: arriving early in cold conditions may reduce survival. First, we show that in female recruits, spring arrival date in the first breeding year correlates positively with hatch date; hence, early-hatched individuals experience colder conditions at arrival than late-hatched individuals. Second, we show that when temperatures at arrival in the recruitment year were high, early-hatched young had a higher recruitment probability than when temperatures were low. We interpret this as a potential cost of arriving early in colder years, and climate warming may have reduced this cost. We thus show that higher temperatures in the arrival year of recruits were associated with stronger selection for early reproduction in the years these birds were born. As arrival temperatures in the beginning of the study increased, but recently declined again, directional selection on timing of reproduction showed a nonlinear change. We demonstrate that environmental conditions with a lag of up to two years can alter selection on phenological traits in natural populations, something that has important implications for our understanding of how climate can alter patterns of selection in natural populations. Pied flycatchers are long-distance migrant birds that have advanced their timing of reproduction over the past decades in response to climate change. We studied selection on egg-laying date using a 31-year-long population study and found that in the first 20 years, early-reproducing birds had increasingly higher fitness than late-reproducing birds, resulting in intensified selection on egg-laying date. However, during the last decade, selection on egg-laying date has weakened considerably, although the timing mismatch between breeding and food availability—supposedly the main determinant of selection on breeding phenology—did not change. Whereas conditions during breeding cannot explain the temporal pattern in the strength of selection, spring temperatures at the time the offspring’s first return to the breeding site, i.e., one or two years later, do explain the annual variation in selection well. If spring temperature at arrival is high, early-hatched birds recruit to the breeding population better than late-hatched birds, while in cold years, early- and late-hatched birds recruit equally well. Because early-hatched daughters arrive early when they recruit into the population, females that lay eggs early (and thus have early-hatched chicks) have a strong selective advantage when the following years are warm. Arrival temperatures increased over the first two decades but then cooled again, leading to the observed pattern in selection.