Climate variability in the North Atlantic has been linked in part to the North Atlantic Oscillation (NAO). The NAO influences marine ecosystems in the northwestern Atlantic and transport variability of the cold Labrador Current. Understanding historic patterns of NAO variability requires long-term and high-resolution climate records that are not available from instrumental data. Here we present the first century-scale proxy record of sea surface temperature (SST) variability from the Newfoundland shelf, a region from which other annual-resolution shallow marine proxies are unavailable. The 116 year record was obtained from three sites along the eastern Newfoundland shelf using laser ablation inductively coupled mass spectrometry-determined Mg/Ca ratios in the crustose coralline alga Clathromorphum compactum. The alga is characterized by a high Mg-calcite skeleton exhibiting annual growth increments and a century-scale lifespan. Results indicate positive correlations between interannual variations in Mg/Ca ratios and both station-based and gridded instrumental SST. In addition, the record shows high spatial correlations to SST across the Newfoundland shelf and the Gulf of St. Lawrence. Before 1950 the Mg/Ca proxy record reveals significant departures from gridded temperature records. While the Newfoundland shelf is generally considered a region of negative correlations to the NAO, the algal time series as well as a recent modeling study suggest a variable negative relationship with the NAO which is strongest after ∼1960 and before the mid-1930s.