Arctic animals face dramatic habitat alteration due to ongoing climate change. Understanding how such species have responded to past glacial cycles can help us forecast their response to today's changing climate. Gray whales are among those marine species likely to be strongly affected by Arctic climate change, but a thorough analysis of past climate impacts on this species has been complicated by lack of information about an extinct population in the Atlantic. While little is known about the history of Atlantic gray whales or their relationship to the extant Pacific population, the extirpation of the Atlantic population during historical times has been attributed to whaling. We used a combination of ancient and modern DNA, radiocarbon dating and predictive habitat modelling to better understand the distribution of gray whales during the Pleistocene and Holocene. Our results reveal that dispersal between the Pacific and Atlantic was climate dependent and occurred both during the Pleistocene prior to the last glacial period and the early Holocene immediately following the opening of the Bering Strait. Genetic diversity in the Atlantic declined over an extended interval that predates the period of intensive commercial whaling, indicating this decline may have been precipitated by Holocene climate or other ecological causes. These first genetic data for Atlantic gray whales, particularly when combined with predictive habitat models for the year 2100, suggest that two recent sightings of gray whales in the Atlantic may represent the beginning of the expansion of this species' habitat beyond its currently realized range.