Global warming is affecting the population dynamics and trophic interactions across a wide range of ecosystems and habitats. Translating these real-time effects into their long-term consequences remains a challenge. The rapid and extreme warming period that occurred after the Last Glacial Maximum (LGM) during the Pleistocene-Holocene transition (7-12 thousand years ago) provides an opportunity to gain insights into the long-term responses of natural populations to periods with global warming. The effects of this post-LGM warming period have been assessed in many terrestrial taxa, whereas insights into the impacts of rapid global warming on marine taxa remain limited, especially for megafauna. In order to understand how large-scale climate fluctuations during the post-LGM affected baleen whales and their prey, we conducted an extensive, large-scale analysis of the long-term effects of the post-LGM warming on abundance and inter-ocean connectivity in eight baleen whale and seven prey (fish and invertebrates) species across the Southern and the North Atlantic Ocean; two ocean basins that differ in key oceanographic features. The analysis was based upon 7032 mitochondrial DNA sequences as well as genome-wide DNA sequence variation in 100 individuals. The estimated temporal changes in genetic diversity during the last 30,000 years indicated that most baleen whale populations underwent post-LGM expansions in both ocean basins. The increase in baleen whale abundance during the Holocene was associated with simultaneous changes in their prey and climate. Highly correlated, synchronized and exponential increases in abundance in both baleen whales and their prey in the Southern Ocean were indicative of a dramatic increase in ocean productivity. In contrast, the demographic fluctuations observed in baleen whales and their prey in the North Atlantic Ocean were subtle, varying across taxa and time. Perhaps most important was the observation that the ocean-wide expansions and decreases in abundance that were initiated by the post-LGM global warming, continued for millennia after global temperatures stabilized, reflecting persistent, long-lasting impacts of global warming on marine fauna.