Ice is one of the most important drivers of population dynamics in polar organisms, influencing the locations, sizes, and connectivity of populations. Antarctic fur seals, Arctocephalus gazella, are particularly interesting in this regard, as they are concomitantly reliant on both ice-associated prey and ice-free coastal breeding areas. We reconstructed the history of this species through the Last Glacial Maximum (LGM) using genomic sequence data from seals across their range. Population size trends and divergence events were investigated using continuous-time size estimation analysis and divergence time estimation models. The combined results indicated that a panmictic population present prior to the LGM split into two small refugial populations during peak ice extent. Following ice decline, the western refugial population founded colonies at the South Shetlands, South Georgia, and Bouvetøya, while the eastern refugial population founded the colony on Iles Kerguelen. Postglacial population divergence times closely match geological estimates of when these coastal breeding areas became ice free. Given the predictions regarding continued future warming in polar oceans, these responses of Antarctic fur seals to past climate variation suggest it may be worthwhile giving conservation consideration to potential future breeding locations, such as areas further south along the Antarctic Peninsula, in addition to present colony areas.