Biological responses to climate and environmental changes in remote polar regions are of increasing interest in global change research. Terrestrial and marine polar ecosystems have suffered from impacts of both rapid climate change and intense human activities, and large fluctuations in the population sizes of seabirds, seals, and Antarctic krill have been observed in the past decades. To understand the mechanisms driving these regime shifts in polar ecosystems, it is important to first distinguish the influences of natural forcing from anthropogenic activities. Therefore, investigations of past changes of polar ecosystems prior to human contact are relevant for placing recent human-induced changes within a long-term historical context. Here we focus our review on the fossil, sub-fossil, archaeological, and biogeochemical remains of marine vertebrates in polar sediments. These remains include well-preserved tissues such as bones, hairs and feathers, and biogeochemical markers and other proxy indicators, including deposits of guano and excrement, which can accumulate in lake and terrestrial sediments over thousands of years. Analyses of these remains have provided insight into both natural and anthropogenic impacts on marine vertebrates over millennia and have helped identify the causal agents for these impacts. Furthermore, land-based seabirds and marine mammals have been shown to play an important role as bio-vectors in polar environments as they transport significant amounts of nutrients and anthropogenic contaminants between ocean and terrestrial ecosystems.