We undertake the first comprehensive effort to integrate North Atlantic marine climate records for the last millennium, highlighting some key components common within this system at a range of temporal and spatial scales. In such an approach, careful consideration needs to be given to the complexities inherent to the marine system. Composites therefore need to be hydrographically constrained and sensitive to both surface water mass variability and three-dimensional ocean dynamics. This study focuses on the northeast (NE) North Atlantic Ocean, particularly sites influenced by the North Atlantic Current. A composite plus regression approach is used to create an inter-regional NE North Atlantic reconstruction of sea surface temperature (SST) for the last 1000 years. We highlight the loss of spatial information associated with large-scale composite reconstructions of the marine environment. Regional reconstructions of SSTs off the Norwegian and Icelandic margins are presented, along with a larger-scale reconstruction spanning the NE North Atlantic. The latter indicates that the ‘Medieval Climate Anomaly’ warming was most pronounced before AD 1200, with a long-term cooling trend apparent after AD 1250. This trend persisted until the early 20th century, while in recent decades temperatures have been similar to those inferred for the ‘Medieval Climate Anomaly’. The reconstructions are consistent with other independent records of sea-surface and surface air temperatures from the region, indicating that they are adequately capturing the climate dynamics of the last millennium. Consequently, this method could potentially be used to develop large-scale reconstructions of SSTs for other hydrographically constrained regions.