This work investigates the association of Atlantic sea surface temperature anomalies (SSTA) with the early winter North Atlantic Oscillation (NAO). The NAO is represented by two indices in November, December, and January. One (regional mean index) is defined as 500 hPa geopotential height difference between areal averages in low and high latitudes, while another (station index) is the sea level pressure difference between two stations. Although the two indices are highly correlated, they exhibit clearly different statistical associations with the antecedent Atlantic SSTA. The regional mean index in early winter is significantly correlated with a tripole pattern of SSTA in the Atlantic up to the preceding spring. Therefore its predictability may be claimed for up to 7--9 months. However there is little predictability for the station index beyond SSTA 2 months before the early winter. The interseasonal potential predictability shown in the regional mean index mainly results from the contribution of a few years that are not strong anomaly years according to the station index. That suggests that the potential predictability displayed in association with the regional mean index mainly results from the average of a few anomaly years. The SSTA contribution to the NAO predictability comes mostly from the North Atlantic and northern subtropical Atlantic. The association of equatorial Atlantic SSTA with the NAO for both indices is insignificant. There is no linear connection between the tropical Atlantic SSTA and the tripole SSTA pattern, and the tropical and North Pacific SSTA may be a factor affecting NAO predictability.