Enhancing the availability and reliability of dielectric ceramic energy storage devices is of great importance. In this work, (1-$x$)${\mathrm{\text{Na}}}_{0.5}{\mathrm{\text{Bi}}}_{0.5}{\mathrm{\text{TiO}}}_3$–$x$Bi(${\mathrm{\text{Mg}}}_{0.5}{\mathrm{\text{Hf}}}_{0.5}$)${\mathrm{\text{O}}}_3$ (NBT–$x$BMH) lead-free ceramics were created utilizing a solid-state reaction technique. All NBT–$x$BMH 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–$x$BMH 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 $W_{\mathrm{\text{rec}}}$ of 4.63 J/${\mathrm{\text{cm}}}^3$ and an $\eta$ 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${}^{\circ }$C). Charge–discharge test shows that the NBT–0.25BMH ceramic has a quick discharge rate ($t_{0.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.