Natal dispersal allows individuals to reach suitable breeding sites. The effect of present plant phenology as a cue for dispersal into areas with favourable stages of development has been well established across avian and mammalian taxa. However, the effect of past experience is less understood. We studied the effect of past and present phenology of the environment on the direction and distance of natal dispersal in a passerine bird, the pied flycatcher (Ficedula hypoleuca). We monitored spring settlement of local recruits in six nest box plots along a 10-km stretch of a south-north gradient of plant and caterpillar food development. We found that males used both past experience of caterpillar phenology from early life and actual plant phenology during the recruitment season as independent cues for breeding settlement. Males that had experienced a mismatch with the caterpillar food peak as a nestling, and/or those that arrived late in the spring in the recruitment year, moved north of their natal site, whereas males that had experienced a better match with the caterpillars as a nestling, and/or those that migrated earlier in the spring, settled at a similar site or more to the south. In females, no such effects were found, suggesting that the usage of phenological cues is sex specific. In summary, tracking environmental phenology by natal dispersal may represent an effective mechanism for settling in new favourable areas, and may thus potentially cause rapid change of a species' geographical breeding range in response to climate change.