Arctic Terns (Sterna paradisaea) share a few routes to undertake the longest annual migrations of any organism. To understand how the wide spatial range of their breeding colonies may affect their migration strategies (e.g., departure date), we tracked 53 terns from five North American colonies distributed across 30° of latitude and 90° of longitude. While birds from all colonies arrived in Antarctic waters at a similar time, terns nesting in the Arctic colonies migrated back north more slowly and arrived to their breeding grounds later than those nesting in the colony farther south. Arrival dates in Antarctic waters coincided with the start of favorable foraging conditions (i.e., increased ocean productivity), and similarly arrival dates at breeding colonies coincided with the start of local favorable breeding conditions (i.e., disappearance of snow and ice). Larger birds followed a more direct southbound migration route than smaller birds. On both southbound and northbound migrations, daily distances traveled declined as time spent in contact with the ocean increased, suggesting a trade-off between resting/foraging and traveling. There was more unexplained variation in behavior among individuals than among colonies, and one individual had a distinctive stop around Brazil. Terns nesting in the Arctic have a narrow time window for breeding that will likely increase with continuing declines in sea ice and snow. Departing Arctic Terns likely have few clues about the environmental conditions they will encounter on arrival, and their response to environmental changes at both poles may be assisted by large individual variation in migration strategy.