Lithium-ion batteries have achieved dominance in energy storage systems. Meanwhile, there is a demand for the reliability of lithium-ion batteries. Battery prognostics and health management (PHM) is a discipline that not only provides accurate, early, and online health diagnosis, but also guarantees a robust and precise prediction of the remaining useful life of lithium-ion batteries, independent of the operating conditions. This paper attempts to develop a novel PHM methodology that addresses the points mentioned above. A large dataset including thirty-eight nickel manganese cobalt oxide battery cells is used. The battery cells have been tested under various test conditions to achieve different aging patterns. Afterward, the health indicators that describe the health trajectory of the battery are extracted from partial charging voltage curves. A recurrent neural network called nonlinear autoregressive with exogenous input is developed to estimate battery state of health (SOH) based on the extracted health indicators. The estimated SOH is used as the prognostic feature to develop a remaining useful life of battery (RUL) prediction model based on the similarity-based model. The proposed methods are validated using untrained data. The results indicate that the proposed PHM methodology can estimate the SOH of untrained battery cells with a maximum RMSE of 0.61. The RUL of battery cells with different aging patterns can be predicted with a maximum absolute error of 110 cycles. It can be concluded that the proposed method has the advantages of high precision in the health diagnosis and prognosis of battery cells regardless of their aging patterns, simplicity, and generalization to untrained data. These advantages point out the feasibility of the proposed method for online prognostics and health management of lithium-ion batteries.