Higher-order predators such as Antarctic seabirds serve as ecological indicators of environmental change and provide a crucial link between marine and terrestrial ecosystems. Despite their prevalence and significance in the Antarctic ecosystem, there is a lack of understanding of the impacts of major regime shifts in paleoclimate on flighted Antarctic seabirds. We address this by reconstructing demographic histories using complete genomes of six flighted seabirds and two penguin species, each with distinct habitat requirements and life histories in East Antarctica. We evaluated changes in species abundance in relation to major environmental shifts after 10 Mya, including previously inferred Antarctic krill abundance. We demonstrated that four fulmarine petrel species increased during periods of paleoclimatic cooling (10 Mya to 500 kya) and prior to krill population increases, potentially reflecting earlier use of alternative prey. Fulmarine petrels increased more rapidly than Adélie and Emperor penguins, likely reflecting their greater ability to exploit resources through flight. Differing from all other species, demographic histories of South Polar Skua and Wilson’s Storm-Petrel exhibited long periods of decline, and these may reflect physiological constraints or may be confounded by aspects of their evolutionary history (e.g., recent speciation and colonisation of Antarctica). Overall, our results indicate a degree of predictability in species’ responses to past climate change. With most species requiring ice-free breeding areas, the predominant observation of increases in predator abundance across a background of climatic cooling suggests that future increase in ice-free areas for breeding may not offset negative impacts from any declines in prey.