Prediction of the Northeast China’s winter surface air temperature (SAT) is investigated in this paper. Following the Fan and Wang (2008) strategy, the year to year increment of the predictand is forecasted first and then the predictand is predicted. Thus, in the first step, the predictors for the increment of winter SAT were determined through analysis on the atmospheric variability that associated with the increment of winter SAT. Then the multi-linear regression was applied to establish a prediction model for the increment of winter SAT in Northeast China. The prediction model shows a high correlation coefficient (0.73) between the simulated and observed the annual increment of winter SAT in Northeast China throughout the period 1965-2002, with the relative root mean square error of -7.9%. The prediction model makes a reasonable hindcast for 2003-2008, with the average relative root mean square error of -7.2%. The prediction model can capture the increasing trend of winter SAT in Northeast China during 1965-2008. The results suggest that the approach to forecasting the annual increment of winter SAT in Northeast China would be feasible in the operational seasonal forecasts.