Current trends in marine ecosystems need to be interpreted against a solid understanding of the magnitude and drivers of past changes. Over the last decade, marine scientists from different disciplines have engaged in the emerging field of marine historical ecology to reconstruct past changes in the sea. Here we review the diversity of approaches used and resulting patterns of historical changes in large marine mammals, birds, reptiles and fish. Across 256 reviewed records, exploited populations declined 89% from historical abundance levels (range: 11-100%). In many cases, long-term fluctuations are related to climate variation, rapid declines to overexploitation and recent recoveries to conservation measures. These emerging historical patterns offer new insights into past ecosystems, and provide important context for contemporary ocean management.