Enhancing the availability and reliability of dielectric ceramic energy storage devices is of great importance. In this work, (1-x)Na0.5Bi0.5TiO3–xBi(Mg0.5Hf0.5)O3 (NBT–xBMH) lead-free ceramics were created utilizing a solid-state reaction technique. All NBT–xBMH ceramics have a single perovskite structure. With increasing BMH doping, the grain size shrinks drastically, which greatly enhances the breakdown electric field (310 kV/cm at x = 0.25). Additionally, the relaxation behaviors of NBT–xBMH ceramics with high BMH content are more remarkable. Among all designed components, the NBT–0.25BMH ceramic exhibits the best energy storage performance with a high Wrec of 4.63 J/cm3 and an η of 75.1% at 310 kV/cm. The NBT–0.25BMH ceramic has exceptional resistance to fluctuations in both frequency (5–500 Hz) and temperature (30–100∘C). Charge–discharge test shows that the NBT–0.25BMH ceramic has a quick discharge rate (t0.9< 110 ns). With these properties, the NBT–0.25BMH ceramic may have applications in microdevices as well as in ultra-high power electronic systems.