Holocene sea surface temperatures (SST) of the Black Sea have been reconstructed using sedimentary C37 unsaturated alkenones assumed to be derived from the coccolithophorid haptophyte Emiliania huxleyi, whose fossil coccoliths are an important constituent of the unit I sediments. However, alkenones can also be biosynthesized by haptophyte species that do not produce microscopic recognizable coccoliths. A species-specific identification of haptophytes is important in such U37K'-based past SST reconstructions since different species have different alkenone-SST calibrations. We showed that 18S rDNA of E. huxleyi made up only a very small percentage (less than 0.8%) of the total eukaryotic 18S rDNA within the up to 3600-year-old fossil record obtained from the depocenter (>2000 m) of the Black Sea. The predominant fossil 18S rDNA was derived from dinoflagellates (Gymnodinium spp.), which are predominant members of the summer phytoplankton bloom in the modern Black Sea. Using a polymerase chain reaction/denaturing gradient gel electrophoresis method selective for haptophytes, we recovered substantial numbers of a preserved 458-base-pair (bp)-long 18S rDNA fragment of E. huxleyi from the Holocene Black Sea sediments. Additional fossil haptophyte sequences were not detected, indicating that the E. huxleyi alkenone-SST calibration can be applied for at least the last ~3600 years. The ancient E. huxleyi DNA was well protected against degradation since the DNA/alkenone ratio did not significantly decrease throughout the whole sediment core and 20% of ~2700-year-old fossil E. huxleyi DNA was still up to 23,000 base pairs long. We showed that fossil DNA offers great potential to study the Holocene paleoecology and paleoenvironment of anoxic deep-sea settings in unprecedented detail.