In order to provide an accurate State-Of-Health (SOH) estimation, a novel estimation method is proposed in this paper. In this work, some battery SOH relate features are selected theoretically, proved and then re-screened mathematically. These features can reflect the battery degeneration from different aspects. Also, a new training set design idea is proposed for Least Squares Support Vector Machine algorithm, thereby a model that is suitable for lithium-ion Battery SOH estimation under multi-working conditions can be built. Several lithium-ion battery degeneration testing datasets from National Aeronautics and Space Administration Ames Prognostics Center of Excellence are used to validate the proposed method. Results demonstrate both the superiority of the proposed method and its potential applicability as an effective SOH estimation method for embedded Battery Management System. •A novel estimation method for State-Of-Health estimation is proposed.•Some features related to battery SOH are selected and re-screened mathematically.•A model for lithium-ion Battery SOH estimation under multi-working conditions is built.