Concerning numbers of Wandering Albatrosses Diomedea exulans are killed when they attempt to scavenge baited hooks deployed by long-line fishing vessels. We studied the foraging ecology of Wandering Albatrosses breeding on Marion Island in order to assess the scale of interactions with known long-line fishing fleets. During incubation and large chick-rearing, birds foraged farther away from the island, in warmer waters, and showed high spatial overlap with areas of intense tuna Thunnus spp. long-line fishing. During small chick-rearing, birds made shorter foraging trips and showed higher spatial overlap with the local Patagonian toothfish Dissostichus eleginoides long-line fishery. Tracks of birds returning with offal from the toothfish fishery, showed a strong association with positions at which toothfish long-lines were set and most diet samples taken during this stage contained fisheries-related items. Independent of these seasonal differences, females foraged farther from the islands and in warmer waters than males. Consequently, female distribution overlapped more with tuna long-line fisheries, whereas males interacted more with the toothfish long-line fishery. These factors could lead differences in the survival probabilities of males and females. Non-breeding birds foraged in warmer waters and showed the highest spatial overlap with tuna long-line fishing areas. The foraging distribution of Marion Island birds showed the highest degree of spatial overlap with birds from the neighbouring Crozet Islands, during the late chick-rearing and non-breeding periods. These areas of foraging overlap also coincided with areas of intense tuna longline fishing, south of Africa. As the population trends of Wandering Albatrosses at these two localities are very similar, it is possible that incidental mortality during the periods when these two populations show the highest spatial overlap could be driving these trends.