Numbers of Gentoo Penguins Pygoscelis papua and Crozet Shags Phalacrocorax [atriceps] melanogenis breeding annually at Marion Island, one of South Africa’s Prince Edward Islands in the south-west Indian Ocean, were strongly correlated over 19 split-years from 1994/95–2012/13. Both species decreased between the mid-1990s and the mid-2000s, exhibited a partial recovery in the late-2000s and then decreased to their lowest recorded levels in 2012/13. In both instances, the partial recoveries in the late-2000s were associated with improved breeding success. At a colony of Gentoo Penguins, breeding success was negatively correlated with the date of arrival of adults to breed. Gentoo Penguins and Crozet Shags are demersal feeders in inshore waters around Marion Island and there is considerable overlap in the compositions of their diets. Therefore, trends in their populations may be driven by food availability, which is likely to be influenced by benthic production around the island. In South Africa and based on the current assessment, the Crozet Shag, which elsewhere breeds only at the Crozet Islands, is now Critically Endangered and the more widely ranging Gentoo Penguin is Endangered.