With the increasing adoption of electric vehicles (EVs) by the general public, a lot of research is being conducted in Li-ion battery-related topics, where state-of-health (SoH) estimation has a prominent role. Accurate knowledge of this parameter is essential for efficient and safe EV operation. In this work, machine-learning techniques are applied to estimate this parameter in EV applications and in diverse scenarios. After thoroughly analysing cell ageing in different storage conditions, a novel approach based on impedance data is developed for SoH estimation. A fully-connected feed-forward neural network (FC-FNN) is employed to estimate the battery’s maximum available capacity from a small set of impedance measurements. The method was tested for estimation in long-term scenarios and for diverse degradation procedures with data from real EV batteries. High accuracy was obtained in all situations, with a mean absolute error as low as 0.9%. Thus, the proposed algorithm constitutes a powerful and viable solution for fast and accurate SoH estimation in real-world battery management systems.