We report on the population changes of five species of Procellariiform seabirds breeding at Marion Island: wandering albatross (Diomedea exulans), grey-headed albatross (Thalassarche chrysostoma), northern giant petrel (Macronectes halli), southern giant petrel (M. giganteus), and white-chinned petrel (Procellaria aequinoctalis). The four large surface-nesting species (wandering albatross, grey-headed albatross and the northern and southern giant petrel) show similar population trends over the last 16-18 years. All were stable or decreasing during the 1980s, followed by a recovery period during the early to mid-1990s. Recently, all species have once again stabilized or decreased in numbers. Population trends of wandering albatross at Marion Island were strongly correlated with other Indian Ocean populations, but were different from the Atlantic Ocean population. These similarities suggest a common cause and can be explained by changes in tuna (Thunnus spp.) longline fishing effort in the southern Indian Ocean. A recent increase in tuna longlining, as well as recent large-scale Illegal, Unregulated and Unreported (IUU) longline fishing for Patagonian toothfish (Dissostichus eleginoides) close to Marion Island, could be contributing to the recent decreases in some of these species. Adoption of mitigation measures and an effective means of dealing with IUU longline fishing seem necessary to reduce the potential impacts of longline fishing on populations of albatross and petrel.