In a highly dynamic airspace, flying animals are predicted to adjust foraging behaviour to variable wind conditions to minimize movement costs. Sexual size dimorphism is widespread in wild animal populations, and for large soaring birds which rely on favourable winds for energy-efficient flight, differences in morphology, wing loading and associated flight capabilities may lead males and females to respond differently to wind. However, the interaction between wind and sex has not been comprehensively tested. We investigated, in a large sexually dimorphic seabird which predominantly uses dynamic soaring flight, whether flight decisions are modulated to variation in winds over extended foraging trips, and whether males and females differ. Using GPS loggers we tracked 385 incubation foraging trips of wandering albatrosses Diomedea exulans, for which males are c. 20% larger than females, from two major populations (Crozet and South Georgia). Hidden Markov models were used to characterize behavioural states—directed flight, area-restricted search (ARS) and resting—and model the probability of transitioning between states in response to wind speed and relative direction, and sex. Wind speed and relative direction were important predictors of state transitioning. Birds were much more likely to take off (i.e. switch from rest to flight) in stronger headwinds, and as wind speeds increased, to be in directed flight rather than ARS. Males from Crozet but not South Georgia experienced stronger winds than females, and males from both populations were more likely to take-off in windier conditions. Albatrosses appear to deploy an energy-saving strategy by modulating taking-off, their most energetically expensive behaviour, to favourable wind conditions. The behaviour of males, which have higher wing loading requiring faster speeds for gliding flight, was influenced to a greater degree by wind than females. As such, our results indicate that variation in flight performance drives sex differences in time–activity budgets and may lead the sexes to exploit regions with different wind regimes.