The development of lead-free ceramics for electrostatic energy storage has attracted great interest because of the growing environmental concerns. Despite the extensive exploration, the unsuccess in synergistically optimizing both energy density and efficiency of polycrystalline materials is the major hurdle for their practical applications. Herein, Bi(Mg0.5Zr0.5)O3-modified BaTiO3 lead-free relaxor ferroelectric ceramics are demonstrated to be viable candidates for energy storage. The materials can simultaneously deliver a high recoverable energy density of 2.9 J cm−3 and a high energy efficiency of 86.8%, which are enhanced by 625% and 156% over those of unmodified BaTiO3, while keeping insensitive to thermal stimulus over 30–150 °C. It is unveiled that the incorporation of Bi(Mg0.5Zr0.5)O3 favors the formation of polar nanoregions (PNRs), as evidenced by transmission electron microscope and piezoresponse force microscopy, which increases the threshold field to induce long range order and decreases the stability thereof, contributing to the more linear-towards polarization behavior. The dynamic PNRs along with the decreased grain size, increased bulk density, and consequently enhanced dielectric breakdown strength (301.4 kV cm−1) are responsible for the superior energy storage performance of Bi(Mg0.5Zr0.5)O3-modified BaTiO3 ceramics. This work opens up a new avenue to tailor lead-free dielectrics toward high energy storage performance for electrical energy storage.