Gray whales (Eschrichtius robustus) undertake long migrations, from Baja California to Alaska, to feed on seasonally productive benthos of the Bering and Chukchi seas. The invertebrates that form their primary prey are restricted to shallow water environments, but global sea-level changes during the Pleistocene eliminated or reduced this critical habitat multiple times. Because the fossil record of gray whales is coincident with the onset of Northern Hemisphere glaciation, gray whales survived these massive changes to their feeding habitat, but it is unclear how.We reconstructed gray whale carrying capacity fluctuations during the past 120,000 years by quantifying gray whale feeding habitat availability using bathymetric data for the North Pacific Ocean, constrained by their maximum diving depth. We calculated carrying capacity based on modern estimates of metabolic demand, prey availability, and feeding duration; we also constrained our estimates to reflect current population size and account for glaciated and non-glaciated areas in the North Pacific. Our results show that key feeding areas eliminated by sea-level lowstands were not replaced by commensurate areas. Our reconstructions show that such reductions affected carrying capacity, and harmonic means of these fluctuations do not differ dramatically from genetic estimates of carrying capacity.Assuming current carrying capacity estimates, Pleistocene glacial maxima may have created multiple, weak genetic bottlenecks, although the current temporal resolution of genetic datasets does not test for such signals. Our results do not, however, falsify molecular estimates of pre-whaling population size because those abundances would have been sufficient to survive the loss of major benthic feeding areas (i.e., the majority of the Bering Shelf) during glacial maxima. We propose that gray whales survived the disappearance of their primary feeding ground by employing generalist filter-feeding modes, similar to the resident gray whales found between northern Washington State and Vancouver Island.