Abstract Arctic marine ecosystems have undergone notable reconfigurations in response to Holocene environmental shifts. Yet our understanding of how marine mammal occurrence was impacted remains limited, due to their relative scarcity in the fossil record. We reconstructed the occurrence of marine mammals across the past 12,000 years through genetic detections based on sedimentary ancient DNA from four marine sediment cores collected around Northern Greenland, and integrated the findings with local and regional environmental proxy records. Our findings indicate a close association between the establishment of marine mammals at densities detectable in marine sediments and the deglaciation of marine environments at the onset of the Holocene. Further, we identified air temperature as a significant driver of community change across time. Several marine mammals were detected in the sediments earlier than in the fossil record, for some species by several thousands of years. During the Early-to-Mid Holocene, a period of past warmer climate, we recorded northward distribution shifts of temperate and low-arctic marine mammal species. Our findings provide unique, long-term baseline data on the occurrence of marine mammals around Northern Greenland, providing novel insights into past community dynamics and the effects of Holocene climatic shifts on the region’s marine ecosystems.