The Pacific Decadal Oscillation (PDO) is a leading mode of decadal sea surface temperature variability in the North Pacific. Skillful PDO prediction can be beneficial in many aspects because of its global and regional impacts. However, current climate models cannot provide satisfied decadal prediction of the PDO and related decadal variability of sea surface temperature. In this study, we propose a new approach, i.e., the increment method, to predicting the PDO. A series of validations demonstrate that the increment method is effective in improving decadal prediction of PDO and it can well capture the phase change of PDO with high accuracy. The prediction processes include three steps. First, a five-year smoothing is performed; second, effective preceding predictors for PDO are selected, with all predictors and predictands in the form of a three-year decadal increment (DI); third, the prediction model is set up for PDO three-year decadal increment (DI_PDO), and PDO prediction can be obtained by adding the predicted DI_PDO to the observed PDO three years ago. This new method can also be applied for decadal climate prediction of other modes (e.g., Atlantic multidecadal oscillation) and predictands (e.g., sea surface temperature).