Gut microbes are increasingly recognised for their role in regulating an animal's metabolism and immunity. However, identifying repeatable associations between host physiological processes and their gut microbiota has proved challenging, in part because microbial communities often respond stochastically to host physiological stress (e.g. fasting, forced exercise or infection). Migratory birds provide a valuable system in which to test host-microbe interactions under physiological extremes because these hosts are adapted to predictable metabolic and immunological challenges as they undergo seasonal migrations, including temporary gut atrophy during long-distance flights. These physiological challenges may either temporarily disrupt gut microbial ecosystems, or, alternatively, promote predictable host-microbe associations during migration. To determine the relationship between migration and gut microbiota, we compared gut microbiota composition between migrating and non-migrating ("resident") conspecific shorebirds sharing a flock. We performed this across two sandpiper species, Calidris ferruginea and Calidris ruficollis, in north-western Australia, and an additional C. ruficollis population 3,000 km away in southern Australia. We found that migrants consistently had higher abundances of the bacterial genus Corynebacterium (average 28% abundance) compared to conspecific residents (average < 1% abundance), with this effect holding across both species and sites. However, other than this specific association, community structure and diversity was almost identical between migrants and residents, with migration status accounting for only 1% of gut community variation when excluding Corynebacterium. Our findings suggest a consistent relationship between Corynebacterium and Calidris shorebirds during migration, with further research required to identify causal mechanisms behind the association, and to elucidate functionality to the host. However, outside this specific association, migrating shorebirds broadly maintained gut community structure, which may allow them to quickly recover gut function after a migratory flight. This study provides a rare example of a repeatable and specific response of the gut microbiota to a major physiological challenge across two species and two distant populations.