Abstract The state-of-health (SOH) of a lithium-ion battery is a key parameter in battery management systems. However, current approaches to estimating the SOH of a lithium-ion battery are mainly offline or have not solved the accuracy and efficiency problems. This paper attempts to solve these problems. A dynamic information extraction method based on a fast discrete wavelet transform is proposed to greatly improve the algorithm efficiency. Dimension reduction is performed on the battery current and voltage time series using the maximum entropy partition method to individually generate a symbolic time series. A cross D-Markov machine model is built based on the causal symbolic time series to extract the feature parameter and represent the lithium-ion battery SOH. An accelerated aging experiment using LiFePO4 batteries is conducted to identify different aging stages. The results show that the feature parameter is an accurate representation of the lithium-ion battery SOH, the maximum error of SOH can be within 0.113, and the average error can be within 0.0509 in the entire battery life cycle. The proposed method is more suitable for online application than the previous method because its computation time is 250–290 times shorter.