Studies incorporating sedimentary ancient DNA (sedaDNA) analyses to investigate paleo-environments have increased considerably over the last few years, and the possibility of utilizing archived sediment cores from previous field campaigns could unlock an immense resource of sampling material for such paleo-investigations. However, sedaDNA research is at a high risk of contamination by modern environmental DNA, as sub-optimal sediment storage conditions may allow for contaminants (e.g., fungi) to grow and become dominant over preserved sedaDNA in the sample. Here, we test the feasibility of sedaDNA analysis applied to archive sediment material from five sites in the North Atlantic, collected between 1994 and 2013. We analyzed two samples (one younger and one older) per site using a metagenomic shotgun approach and were able to recover eukaryotic sedaDNA from all samples. We characterized the authenticity of each sample through sedaDNA fragment size and damage analyses, which allowed us to disentangle sedaDNA and contaminant DNA. Although we determined that contaminant sequences originated mainly from Ascomycota (fungi), most samples were dominated by Emiliania huxleyi, a haptophyte species that commonly blooms in the study region. We attribute the presence of contaminants to non-ideal sampling and sample storage conditions of the investigated samples. Therefore, while we demonstrate that sedaDNA analysis of archival North Atlantic seafloor sediment samples are generally achievable, we stress the importance of best-practice ship-board sampling techniques and storage conditions to minimize contamination. We highly recommend the application of robust bioinformatic tools that help distinguish ancient genetic signals from modern contaminants, especially when working with archive material.