Climate shifts are key drivers of ecosystem change. Despite the critical importance of Antarctica and the Southern Ocean for global climate, the extent of climate-driven ecological change in this region remains controversial. In particular, the biological effects of changing sea ice conditions are poorly understood. We hypothesize that rapid postglacial reductions in sea ice drove biological shifts across multiple widespread Southern Ocean species. We test for demographic shifts driven by climate events over recent millennia by analyzing population genomic datasets spanning 3 penguin genera (Eudyptes, Pygoscelis, and Aptenodytes). Demographic analyses for multiple species (macaroni/royal, eastern rockhopper, Adélie, gentoo, king, and emperor) currently inhabiting southern coastlines affected by heavy sea ice conditions during the Last Glacial Maximum (LGM) yielded genetic signatures of near-simultaneous population expansions associated with postglacial warming. Populations of the ice-adapted emperor penguin are inferred to have expanded slightly earlier than those of species requiring ice-free terrain. These concerted high-latitude expansion events contrast with relatively stable or declining demographic histories inferred for 4 penguin species (northern rockhopper, western rockhopper, Fiordland crested, and Snares crested) that apparently persisted throughout the LGM in ice-free habitats. Limited genetic structure detected in all ice-affected species across the vast Southern Ocean may reflect both rapid postglacial colonization of subantarctic and Antarctic shores, in addition to recent genetic exchange among populations. Together, these analyses highlight dramatic, ecosystem-wide responses to past Southern Ocean climate change and suggest potential for further shifts as warming continues.