The timing of migration and migratory steps is highly relevant for fitness. Because environmental conditions vary between years, the optimal time for migration varies accordingly. Therefore, migratory animals could clearly benefit from acquiring information as to when it is the best time to migrate in a specific year. Thus, environmental predictability and variability are fundamental characteristics of migration systems but their relationship and consequence for migratory progression has remained unexplored. We develop a simple dynamic model to identify the optimal migration behaviour in environments that differ in predictability, variability and the number of intermediate stop-over sites. Our results indicate that higher predictability along migration routes enables organisms to better time migration when phenology deviates from its long-term average and thus, increases fitness. Information is particularly valuable in highly variable environments and in the final migration-step, i.e. before the destination. Furthermore, we show that a general strategy for obtaining information in relatively uninformative but variable environments is using intermediate stop-over sites that enable migrants to better predict conditions ahead. Our study contributes to a better understanding of the relationship between animal movement and environmental predictability—an important, yet underappreciated factor that strongly influences migratory progression.