The globally warm climate of the early Pliocene gradually cooled from 4 million years ago, synchronous with decreasing atmospheric CO2 concentrations. In contrast, palaeoceanographic records indicate that the Nordic Seas cooled during the earliest Pliocene, before global cooling. However, a lack of knowledge regarding the precise timing of Nordic Seas cooling has limited our understanding of the governing mechanisms. Here, using marine palynology, we show that cooling in the Nordic Seas was coincident with the first trans-Arctic migration of cool-water Pacific mollusks around 4.5 million years ago, and followed by the development of a modern-like Nordic Seas surface circulation. Nordic Seas cooling precedes global cooling by 500,000 years; as such, we propose that reconfiguration of the Bering Strait and Central American Seaway triggered the development of a modern circulation in the Nordic Seas, which is essential for North Atlantic Deep Water formation and a precursor for more widespread Greenland glaciation in the late Pliocene.