A high resolution account of Icelandic sea ice over the last millennium has been constructed using a novel proxy based on the presence in sediments of a biomarker (IP25) produced by sea ice algae. Comparison with historical sea ice records demonstrates a strong correlation between documented sea ice Occurrences and the IP25 proxy. An excellent agreement is also observed between the IP25 record and a diatom-based sea surface temperature reconstruction obtained from the same core and the Crowley and Lowery Northern Hemisphere temperature reconstruction. Using this approach, we provide new historical sea ice data for periods where records are scarce or absent and evidence for abrupt changes to sea ice and/or climate conditions around Iceland during the Little Ice Age.