Rapid global warming is severely impacting Arctic ecosystems and is predicted to transform the abundance, distribution and genetic diversity of Arctic species, though these linkages are poorly understood. We address this gap in knowledge using palaeogenomics to examine how earlier periods of global warming influenced the genetic diversity of Atlantic walrus (Odobenus rosmarus rosmarus), a species closely associated with sea ice and shallow-water habitats. We analysed 82 ancient and historical Atlantic walrus mitochondrial genomes (mitogenomes), including now-extinct populations in Iceland and the Canadian Maritimes, to reconstruct the Atlantic walrus' response to Arctic deglaciation. Our results demonstrate that the phylogeography and genetic diversity of Atlantic walrus populations was initially shaped by the last glacial maximum (LGM), surviving in distinct glacial refugia, and subsequently expanding rapidly in multiple migration waves during the late Pleistocene and early Holocene. The timing of diversification and establishment of distinct populations corresponds closely with the chronology of the glacial retreat, pointing to a strong link between walrus phylogeography and sea ice. Our results indicate that accelerated ice loss in the modern Arctic may trigger further dispersal events, likely increasing the connectivity of northern stocks while isolating more southerly stocks putatively caught in small pockets of suitable habitat.