Climate change has marked effects on global weather patterns and oceanic systems, impacting animal behaviour and fitness in potentially profound ways. Despite this, we lack detailed information about species' responses to climatic variation. Using an 11year tracking dataset of over 300 individual birds, we explore the consequences of variation in the southern annular mode (SAM) and southern oscillation index (SOI) for individual behaviour and fitness in wandering albatrosses Diomedea exulans breeding in the Southern Indian Ocean. Our results reveal distinct responses between males and females to climatic variation that align with the impacts of each climatic index on the distinct foraging ranges of each sex. In positive SAM phases, linked to poorer foraging conditions in female ranges and better conditions in male ranges, females exhibited behaviour consistent with reduced foraging success: that is, fewer prey capture attempts and more movement between feeding patches. Males, on the other hand, showed no behavioural change. During positive SOI phases, associated with good foraging conditions in both male and female foraging ranges, both sexes showed evidence of more successful foraging, with birds engaging in more search behaviour, and taking shorter trips with fewer prey capture attempts, together indicating increased food intake per unit time. We found limited evidence for a role of individual variation, as measured through differences in personality, suggesting that plastic responses to climate are sufficiently important so as to obscure inter-individual variation. Supporting this was the finding that individual breeding success was unaffected by climatic variation, suggesting that plastic foraging behaviour allows albatrosses to mitigate climate impacts and maintain reproductive output.