Lead-free dielectric ceramics can be used to make quick charge–discharge capacitor devices due to their high power density. Their use in advanced electronic systems, however, has been hampered by their poor energy storage performance (ESP), which includes low energy storage efficiency and recoverable energy storage density (Wrec). In this work, we adopted a combinatorial optimization strategy to improve the ESP in (Bi0.5Na0.5)TiO3 (BNT)-based relaxor ferroelectric ceramics. To begin, the Bi-containing complex ions Bi(Mg2/3Nb1/3)O3 (BMN) were introduced into a BNT-based matrix in order to improve the diffuse phase transition, increase Bi−O bond coupling, avoid macro domain development, and limit polarization response hysteresis. Second, the viscous polymer process was employed to reduce sample thickness and porosity, resulting in an apparent increase in breakdown strength in (1 − x)[0.7(Bi1/2Na1/2)TiO3]-0.3SrTiO3-xBi(Mg2/3Nb1/3)O3 (BS-xBMN) ceramics. Finally, in x = 0.20 composition, an amazing Wrec of 5.62 J·cm−3 and an ultra-high efficiency of 91.4% were simultaneously achieved at a relatively low field of 330 kV·cm−1, together with remarkable temperature stability in the temperature range of 30–140 °C (3.5 J·cm−3 ± 5% variation). This research presents a new lead-free dielectric material with superior ESP for use in pulsed power capacitors.