Spatial modelling studies stress the importance of predicting future species distribution in changing environments, but it is also important to establish historical distribution ranges of species to provide baseline conditions for understanding distribution shifts. We focused on pelagic ecosystems, the largest ecosystem on Earth. Based on boosting algorithms, we reconstructed the foraging patterns of an oceanic predator, wandering albatross Diomedea exulans, in the highly dynamic Southern Ocean over the last half century. To access the unobserved past oceanographic conditions, we used simulations of the OPA-PISCES oceanic model for the 1958-2001 period. Firstly, we validated the simulated oceanographic variables (sea surface temperature and height, wind speed and chlorophyll a) for the 1998-2001 period with remotely sensed oceanographic data, which were highly correlated, except chlorophyll a. Secondly, we developed two habitat models (based on simulated and observed oceanographic variables) describing the foraging probability of albatrosses. We detected no statistically significant differences between the two models and predictions of both models matched the observed distribution patterns reasonably. Finally, we projected the most likely historical key pelagic habitats of albatross for the 1958 to 2001 period and characterised recurrent, occasional and unfavourable foraging areas in a decadal basis based on average predictions and their standard deviations. Our findings (1) provided a historical baseline (1958-1968) of recurrent, occasional and unfavourable foraging habitats, (2) evidenced a progressive habitat shift the following decades driven by a propagation of sea surface height from SE South Africa towards Antarctica from 1958 to 2001and (3) measured habitat change rates of wandering albatross over the last half century. To our knowledge, our study provides the first quantitative long-term assessment of the spatial response of a marine top predator to changing pelagic habitats of the Southern Ocean and highlighted the oceanographic mechanisms involved, offering new insights on future effects of climate change on the pelagic realm.