Sea ice is a crucial component of the Arctic climate system, yet the tools to document the evolution of sea ice conditions on historical and geological time scales are few and have limitations. Such records are essential for documenting and understanding the natural variations in Arctic sea ice extent. Here we explore sedimentary ancient DNA (aDNA), as a novel tool that unlocks and exploits the genetic (eukaryote) biodiversity preserved in marine sediments specifically for past sea ice reconstructions. Although use of sedimentary aDNA in paleoceanographic and paleoclimatic studies is still in its infancy, we use here metabarcoding and single-species quantitative DNA detection methods to document the sea ice conditions in a Greenland Sea marine sediment core. Metabarcoding has allowed identifying biodiversity changes in the geological record back to almost ~100,000 years ago that were related to changing sea ice conditions. Detailed bioinformatic analyses on the metabarcoding data revealed several sea-ice-associated taxa, most of which previously unknown from the fossil record. Finally, we quantitatively traced one known sea ice dinoflagellate in the sediment core. We show that aDNA can be recovered from deep-ocean sediments with generally oxic bottom waters and that past sea ice conditions can be documented beyond instrumental time scales. Our results corroborate sea ice reconstructions made by traditional tools, and thus demonstrate the potential of sedimentary aDNA, focusing primarily on microbial eukaryotes, as a new tool to better understand sea ice evolution in the climate system.