As electric vehicles (EVs) have been popularized, research on battery management systems (BMSs) in their core technology has drawn considerable attention. Among the various functions of a BMS, estimating the state-of-health (SOH) of the battery is crucial; this estimation is used to determine the replacement time of the battery or to assess driving mileage. While most studies utilize capacity fading or resistance growth as SOH metrics, they all define SOH using fairly constrained assumptions, e.g., full cycling with constant current. Unfortunately, those assumptions cannot be applied to EV batteries that are, for the most part, cycled partially and dynamically. In clear contrast, this paper studies how SOH can be estimated in more practical environments where the batteries must support real-world driving patterns. In particular, this paper proposes a data-driven approach to trace SOH on the fly by using sensible BMS data such as current, voltage, and temperature while leveraging their historical distributions. We validated that our approach provides highly accurate results under actual EV driving conditions, with an average error less than 2.18%. (C) 2016 Elsevier Ltd. All rights reserved.