PROXY temperature records from Greenland ice cores(1,2) and North Atlantic sediment cores(3) have provided evidence for a high degree of climate instability during the last glacial period. Much of this variability seems to be linked with the dynamics of the Laurentide ice sheet that covered North America at this time(3), which discharged iceberg flotillas into the North Atlantic that are now recorded in sediment cores as Heinrich events(4). How (if at all) this variability was manifested on the other side of the Atlantic-in the Nordic seas and the ice sheets of northwest Europe and Scandinavia-has been unclear. Here we present sediment, microfossil and oxygen isotope data from a sediment core in the Norwegian sea, which reveal cooling events and iceberg discharges analogous to Heinrich events. We show that these climate fluctuations in the Norwegian Sea were in phase, or were phase-locked, with air temperatures over Greenland, suggesting that the rapid changes in heat fluxes in the North Atlantic recorded in previous records(3) were felt in this high-latitude region. The iceberg discharges in our record seem to have come from the Fennoscandian ice sheet, implying that this and the Laurentide ice sheets fluctuated coherently on timescales shorter than those of Milankovitch orbital cycles.