Migration of organisms (or cells) is typically an adaptive response to spatiotemporal variation in resources that requires individuals to detect and respond to long-range and noisy environmental gradients. Many organisms, from wildebeest to bacteria, migrate en masse in a process that can involve a vast number of individuals. Despite the ubiquity of collective migration, and the key function it plays in the ecology of many species, it is still unclear what role social interactions play in the evolution of migratory strategies. Here, we explore the evolution of migratory behavior using an individual-based spatially explicit model that incorporates the costs and benefits of obtaining directional cues from the environment and evolvable social interactions among migrating individuals. We demonstrate that collective migratory strategies evolve under a wide range of ecological scenarios, even when social encounters are rare. Although collective migration appears to be a shared navigational process, populations typically consist of small proportions of individuals actively acquiring directional information from their environment, whereas the majorities use a socially facilitated movement behavior. Because many migratory species face severe threat through anthropogenic influences, we also explore the microevolutionary response of migratory strategies to environmental pressures. We predict a gradual decline of migration due to increasing habitat destruction and argue that much greater restoration is required to recover lost behaviors (i.e., a strong hysteresis effect). Our results provide insights into both the proximate and ultimate factors that underlie evolved migratory behavior in nature.