Sea ice is a key factor for the functioning and services provided by polar marine ecosystems. However, ecosystem responses to sea-ice loss are largely unknown because time-series data are lacking. Here, we use shotgun metagenomics of marine sedimentary ancient DNA off Kamchatka (Western Bering Sea) covering the last ~20,000 years. We traced shifts from a sea ice-adapted late-glacial ecosystem, characterized by diatoms, copepods, and codfish to an ice-free Holocene characterized by cyanobacteria, salmon, and herring. By providing information about marine ecosystem dynamics across a broad taxonomic spectrum, our data show that ancient DNA will be an important new tool in identifying long-term ecosystem responses to climate transitions for improvements of ocean and cryosphere risk assessments. We conclude that continuing sea-ice decline on the northern Bering Sea shelf might impact on carbon export and disrupt benthic food supply and could allow for a northward expansion of salmon and Pacific herring.