Wave climate across the ocean basins can be described using satellite altimetry; here, we concentrate on the North Atlantic region. Waves in the North Atlantic are strongly seasonal and peak in the winter season. The northeastern sector of the Atlantic and adjoining shelf seas also exhibit exceptionally high interannual variability in the winter, with monthly average significant wave height varying by up to a factor of 2 from one year to the next. The strength and geographical distribution of variability is broadly consistent throughout the winter months (December--March). A large fraction of these wave height anomalies is associated with a single pattern of pressure anomalies that resembles the North Atlantic Oscillation (NAO). A predictor based on NAO dependence is trained from relatively recent satellite data and then tested against earlier satellite and in situ data. The predictor is successful in large areas of the North Atlantic, confirming a robust relationship between wave height anomalies and the NAO over the last few decades. A substantial rise (up to 0.6 m) in monthly mean wave heights on the northeastern Atlantic during the latter part of the twentieth century is attributable to changes in the NAO. Substantial residual anomalies in wave heights exist after the influence of the NAO has been subtracted; these are partly explained by a second pair of North Atlantic patterns in wave height anomalies and sea level pressure anomalies. This East Atlantic pattern is particularly influential in midwinter and affects the southern part of the northeastern sector (including the region of Seven Stones Light Vessel).