Scattered and indirect evidence suggests that sea ice occurred as far south as the Iceland Sea during the Early Pliocene, when the global climate was warmer than present. However, conclusive evidence as well as potential mechanisms governing sea ice occurrence outside the Arctic Ocean during a time with elevated greenhouse gas concentrations are still elusive. Here we present a suite of organic biomarkers and palynological records from the Iceland Sea and Yermak Plateau. We show that sea ice appeared as early as ~4.5 Ma in the Iceland Sea. The sea ice either occurred seasonally or was transported southward with the East Greenland Current. The Yermak Plateau mostly remained free of sea ice and was influenced dominantly by Atlantic water. From ~4.0 Ma, occurrence of extended sea ice conditions at both the Yermak Plateau and Iceland Sea document a substantial expansion of sea ice in the Arctic. The expansion occurred contemporaneous with increased northward heat and moisture transport in the North Atlantic region, which likely led to a fresher Arctic Ocean that favors sea ice formation. This extensive sea ice cover along the pathway of the East Greenland Current gradually isolated Greenland from warmer Atlantic water in the Late Pliocene, providing a positive feedback for ice sheet expansion in Greenland.