A fundamental question in migration biology is how birds decide when to start their journey, given that arriving too early or too late in a variable environment reduces individual fitness. Internal circannual regulation, and predictable cues such as photoperiod, prepare birds for migration, while variable external cues such as temperature and wind are thought to fine-tune departure times; however, this has not been demonstrated at the key point where an individual animal decides to start its migration. In theory, environmental cues correlated between departure and arrival sites allow informed departure decisions. For 48 satellite-tracked Asian houbara Chlamydotis macqueenii, a medium-distance migrant with climatic connectivity between wintering and breeding areas, each tracked across multiple years, spring departure was under individually-consistent temperature conditions, with greater individual repeatability than for photoperiod or wind. Individuals occupied a range of wintering sites latitudinally spanning 1,200 km, but departed from more northerly latitudes at lower temperatures. These individual departure decisions produced earlier mean population-level departure and arrival dates in warmer springs. Phenological adjustments were fully compensatory, as individuals arrived on the breeding grounds under similar temperature conditions each year. Individuals’ autumn departure decisions were also highly repeatable relative to temperature, but were less distinct than for spring, likely due to relaxed time constraints to leave breeding grounds or reach wintering sites, and use of autumn wind as a supplementary departure cue. Here we have shown that individual-level departure decisions informed by local temperatures can pre-adapt a population to adjust its population-level phenology in response to annual variability in springs timings without genetic change in reaction thresholds.