The Earth's climate is undergoing rapid warming, unprecedented in recent times, which is driving shifts in the distribution and phenology of many plants and animals. Quantifying changes in breeding phenology is important for understanding how populations respond to these changes. While data on shifts in phenology are common for Northern Hemisphere species (especially birds), there is a dearth of evidence from the Southern Hemisphere, and even fewer data available from the marine environment. Surface air temperatures at Macquarie Island have increased by 0.62°C during the 30-year study period (0.21°C decade−1) and royal penguins (Eudyptes schlegeli) commenced egg laying on average three days earlier in the 1990s than during the 1960s. This contrasts with other studies of Southern Ocean seabirds; five of nine species are now breeding on average 2.1 days later than during the 1950s. Despite the different direction of these trends, they can be explained by a single underlying mechanism: resource availability. There was a negative relationship between the Southern Annular Mode (SAM) and median laying date of royal penguins, such that low-productivity (low SAM) years delayed laying date. This accords with the observations of other seabird species from the Antarctic, where later laying dates were associated with lower sea ice and lower spring productivity. The unifying factor underpinning phenological trends in eastern Antarctica is therefore resource availability; as food becomes scarcer, birds breed later. These changes are not uniform across the region, however, with resource increases in the subantarctic and decreases in eastern Antarctica.