The rapid development of battery technology has promoted the deployment of electric vehicles (EVs). To ensure the healthy and sustainable development of EVs, it is urgent to solve the problems of battery safety monitoring, residual value assessment, and predictive maintenance, which heavily depends on the accurate state-of-health (SOH) estimation of batteries. However, many published methods are unsuitable for actual vehicle conditions. To this end, a data-driven method based on the random partial charging process and sparse Gaussian process regression (GPR) is proposed in this article. First, the random capacity increment sequences (oQ) at different voltage segments are extracted from the partial charging process. The average value and standard deviation of oQ are used as features to indicate battery health. Second, correlation analysis is conducted for three types of batteries, and high correlations between the features and battery SOH are verified at different temperatures and discharging current rates. Third, by using the proposed features as inputs, sparse GPR models are constructed to estimate the SOH. Compared with other data-driven methods, the sparse GPR has the highest estimation accuracy, and its average maximum absolute errors are only 2.88%, 2.52%, and 1.51% for three different types of batteries, respectively.