The relationship between the North Atlantic Oscillation (NAO) and Atlantic sea surface temperature (SST) variability is investigated using models and observations. Coupled climate models are used in which the ocean component is either a fully dynamic ocean or a slab ocean with no resolved ocean heat transport. On time scales less than 10 yr, NAO variations drive a tripole pattern of SST anomalies in both observations and models. This SST pattern is a direct response of the ocean mixed layer to turbulent surface heat flux anomalies associated with the NAO. On time scales longer than 10 yr, a similar relationship exists between the NAO and the tripole pattern of SST anomalies in models with a slab ocean. A different relationship exists both for the observations and for models with a dynamic ocean. In these models, a positive (negative) NAO anomaly leads, after a decadal-scale lag, to a monopole pattern of warming (cooling) that resembles the Atlantic multidecadal oscillation (AMO), although with smaller-than-observed amplitudes of tropical SST anomalies. Ocean dynamics are critical to this decadal-scale response in the models. The simulated Atlantic meridional overturning circulation (AMOC) strengthens (weakens) in response to a prolonged positive (negative) phase of the NAO, thereby enhancing (decreasing) poleward heat transport, leading to broad-scale warming (cooling). Additional simulations are used in which heat flux anomalies derived from observed NAO variations from 1901 to 2014 are applied to the ocean component of coupled models. It is shown that ocean dynamics allow models to reproduce important aspects of the observed AMO, mainly in the Subpolar Gyre.