Four cores raised from the eastern Norwegian Sea and adjacent Norwegian fjords at sites influenced by Atlantic water have been investigated. Oxygen isotope analyses in benthic and planktonic foraminifera are used as a proxy for the paleotemperature development spanning the last 800 years. The cores have been dated using a combination of 210Pb and radiocarbon dates yielding time resolutions of 2--5 years for the last century and 9--25 years beyond this. The proxy records have been compared with instrumental time series covering the last 100 years in order to validate the oxygen isotope measurements as a proxy for paleotemperature. The comparison shows that the paleotemperature variability derived from the oxygen isotope analyses is generally similar to the amplitudes and trends seen in the instrumental time series. In particular, a cooling around 1905--1925 followed by a warming until 1955 is evident in all proxy records as well as in the instrumental time series. Beyond the last century the proxy records show two periods from ~1225--1450 and ~1650--1905(25) when temperatures were 1.3--1.6¿C lower than present separated by a period of temperatures periodically comparable to present. The last 80 years represent the modern warming and appear to be the warmest period of the last 800 years. We find that that the ocean temperature variability is comparable to terrestrial reconstructions from the region implying a strong link in the ocean-atmosphere climate system. This suggests that the climate variability in this region beyond the period covered by instrumental time series was also associated with changes in the thermohaline circulation.