Dinoflagellate cyst (dinocyst) records from the southern Nordic Seas were compiled in order to evaluate the evolution of upper ocean conditions, on a millennial timescale and supported by a highly resolved record from the Vøring Plateau. After the transitional phase from the last deglaciation, three main phases define the Holocene. The early Holocene (>7.5 ka BP) features important numbers of cool-temperate species dominated by Nematosphaeropsis labyrinthus and Impagidinium pallidum in the west. The assemblage composition changes drastically at the transition from the early to the mid-Holocene, from when on Operculodinium centrocarpum dominates. The changeover is dated between ~6.1 and 7.5 ka BP, perhaps earlier closer to the Iceland–Scotland Ridge, and appears to be linked to the onset of a modern type of surface circulation. ‘Warmest’ assemblages occur at the Vøring Plateau shortly after the transition, when Atlantic waters also appear to have spread farthest westward. The recurrence of colder elements can be linked to cooling from ~2.4 ka BP at the Vøring Plateau and presumably earlier in the west but is difficult to date there because of the low sedimentation rates. This is a general issue in many areas of the Nordic Seas and appears to have an important effect on cyst concentrations and assemblage composition, with the possible loss of oxygenation-sensitive cysts in the older parts of the cores. Comparing dinocyst-based quantitative reconstructions with those retrieved from other plankton reveals a significantly different trend between proxies, linked to a differing autecological response to seasonal changes at their respective depth habitats.