Dinoflagellate cyst analysis has been conducted on a sediment core from the northern Barents Sea margin (Eastern Arctic Ocean) to reconstruct sea-surface conditions during marine isotope stage 5. Cyst concentrations and composition of assemblages display a distinct variability reflecting deglacial warming and the onset of relatively warm interglacial conditions in early stage 5. Dinoflagellate cyst assemblages of the last interglacial, which corresponds broadly to substage 5e, are comparable with those from recent sediments of the area, but have lower abundances of cold water taxa. Such assemblages suggest that sea-surface temperatures of the last interglacial were therefore at least as warm as today or even warmer. After a distinct cooling, relatively stable cold conditions with minor periods of surface water warming prevailed from mid substages 5d to 5b. Temperatures might have been similar in substages 5a and 5e, but the different compositions of assemblages indicate a stronger stratification of surface waters, probably due to a larger meltwater supply, in substage 5a. These results are compared with previous studies on marine carbonate and calcareous microfossil records from the Fram Strait and Yermak Plateau area, which show that the general view of a cold last interglacial in the Eastern Arctic Ocean is untenable.