Accurate state-of-health (SOH) prediction of lithium-ion batteries (LIBs) plays an important role in improving the performance and assuring the safe operation of the battery energy storage system (BESS). Deep extreme learning machine (DELM) optimized by the improved sparrow search algorithm (ISSA) is developed to predict the SOH of LIBs under random load conditions in the paper. Firstly, two indirect health indicators are extracted from the random partial discharging voltage and current data, which are chosen as the inputs of DELM by the Pearson correlation analysis. Then, ISSA is presented by combining the elite opposition-based learning (EOBL) and the Cauchy-Gaussian mutation strategy to increase the diversity of sparrow populations and prevent them from falling into the local optimization. Finally, the ISSA-DELM model is utilized to estimate the battery SOH. Experimental results illustrate the high accuracy and strong robustness of the proposed approach compared with other methods.