Lithium-ion (Li-ion) batteries have become the dominant choice for powering the Electric Vehicles (EVs). In order to guarantee the safety and reliability of the battery pack in an EV, the Battery Management System (BMS) needs information regarding the battery State of Health (SOH). This paper estimates the battery SOH from the optimal partial charging voltage profiles, which is a straightforward and effective solution for the EV applications. In order to further improve the accuracy and efficiency of the SOH estimation, a novel method optimizing single and multiple voltage ranges during the EV charging process is proposed in this paper. Non-dominated Sorting Genetic Algorithm II (NSGA-II) is applied to automatically select the optimal multiple voltage ranges, while the grid search technique is used to find the optimal single voltage range. The non-dominated solutions from NSGA-II enable the SOH estimation at different battery charging stages, which gives more freedom to the implementation of the proposed method. Three Nickel Manganese Cobalt (NMC)-based batteries from EV, which have been aged under calendar ageing for 360 days, are used to validate the proposed method.