Seasonal and annual climate variations are linked to fluctuations in the abundance and distribution of resources, posing a significant challenge to animals that need to adjust their foraging behavior accordingly. Particularly during adverse conditions, and while energetically constrained when breeding, animals ideally need to be flexible in their foraging behavior. Such behavioral plasticity may separate "winners" from "los-ers" in light of rapid environmental changes due to climate change. Here, the foraging behavior of four sub-Antarctic albatross species was investigated from 2015/16 to 2017/18, a period characterized by pronounced environmental variability. Over three breeding seasons on Marion Island, Prince Edward Archipelago, incubating wandering (WA, Diomedea exulans; n = 45), grey-headed (GHA, Thalassarche chrysostoma; n = 26), sooty (SA, Phoebetria fusca; n = 23), and light-mantled (LMSA, P. palpebrata; n = 22) albatrosses were tracked with GPS loggers. The response of birds to environmental variability was investigated by quantifying interannual changes in their foraging behavior along two axes: spatial distribution, using kernel density analysis, and foraging habitat preference, using generalized additive mixed models and Bayesian mixed models. All four species were shown to respond behaviorally to environmental variability, but with substantial differences in their foraging strategies. WA was most general in its habitat use defined by sea surface height, eddy kinetic energy, wind speed, ocean floor slope, and sea-level anomaly, with individuals foraging in a range of habitats. In contrast, the three smaller albatrosses exploited two main foraging habitats, with habitat use varying between years. Generalist habitat use by WA and interannually variable use of habitats by GHA, SA, and LMSA would likely offer these species some resilience to predicted changes in climate such as warming seas and strengthening of westerly winds. However, future investigations need to consider other life-history stages coupled with demographic studies, to better understand the link between behavioral plasticity and population responses.