Abstract The demography of baleen whales and their prey during the past 30 thousand years was assessed to understand the effects of past rapid global warming on marine ecosystems. Mitochondrial and genome-wide DNA sequence variation in eight baleen whale and seven prey species revealed strong, ocean-wide demographic changes that were correlated with changes in global temperatures and regional oceanographic conditions. In the Southern Ocean baleen whale and prey abundance increased exponentially and in apparent synchrony, whereas changes in abundance varied among species in the more heterogeneous North Atlantic Ocean. The estimated changes in whale abundance correlated with increases in the abundance of prey likely driven by reductions in sea-ice cover and an overall increase in primary production. However, the specific regional oceanographic environment, trophic interactions and species ecology also appeared to play an important role. Somewhat surprisingly the abundance of baleen whales and prey continued to increase for several thousand years after global temperatures stabilized. These findings warn of the potential for dramatic, long-term effects of current climate changes on the marine ecosystem. One Sentence Summary The effects of past global warming on marine ecosystems were drastic, system-wide and long-lasting.