The high-entropy strategy has demonstrated significant advantages in improving the recoverable energy storage density (W_rec) and efficiency (η) of lead-free dielectric capacitors. However, exploring high-performance ceramics within the vast composition space of high-entropy systems using traditional trial-and-error methods remains highly challenging and inefficient. In this study, we employed a machine learning (ML)-accelerated strategy to overcome this limitation. A random forest regression model was developed using a dataset of BaTiO₃ (BT)-based ceramics. Combined with the expected improvement acquisition function, this approach enabled efficient navigation through a space of 660,000 candidate compositions, markedly reducing the experimental burden compared with conventional methods. The optimal composition guided by ML, Ba_0.24Sr_0.24Bi_0.26Na_0.26Ti_0.85Zr_0.15O₃, was experimentally verified to lie in the crossover region between relaxor ferroelectrics and superparaelectrics. In this region, the synergistic coexistence of nanodomains and polar nanoclusters leads to a large polarization difference between the maximum polarization and the remnant polarization (ΔP = P_max − P_r), which is the structural origin of the ultrahigh W_rec of 10.8 J·cm⁻³ and high η of 86%. Furthermore, its excellent charge–discharge performance and stability in terms of temperature and frequency highlight its potential for practical applications, demonstrating the efficacy of machine learning in advancing energy storage ceramics.