A predictor-corrector (P-C) scheme based on the use of rational approximants of second-order to the matrixexponential term in a three-time level reccurence relation is applied to the nonlinear Klein-Gordon equation. This scheme is accelerated by using a modification (MPC) in which the already evaluated values are used for the corrector. Both the predictor and the corrector scheme are analyzed for local truncation error and stability. The proposed method is applied to problems possessing periodic, kinks and single, double-soliton waves. The accuracy as well as the long time behavior of the proposed scheme is discussed.