This paper presents a new online method for state-of charge (SoC) estimation of Lithium-ion (Li-ion) batteries based on sparse Gaussian process regression (GPR). Building upon sparse approximation of the regular GPR, the proposed method is computationally more efficient. The battery SoC is estimated based on measured voltage, current and temperature. The accuracy of the proposed method is verified using LiMn2O4/hardcarbon battery data collected from a constant-current discharge test. In addition, the estimation performance of the proposed method is compared with a SoC estimation method using regular GPR with different covariance functions.