Sodium niobate (NaNbO3)-based lead-free ceramics have been actively studied for energy storage applications because of their antiferroelectric and/or relaxor features achieved in modified systems. The P-E loops of NaNbO3-based ceramics are usually hysteretic because of the existence of a metastable ferroelectric phase at room temperature. In this study, by introducing aliovalent cations and A-site vacancies, the relaxor characteristics are greatly enhanced in (Na1-2xBix)(Nb1-xZrx)O3 ceramics, leading to a high energy storage efficiency of above 90%. In addition, sintering aid CuO and a special ramp-to-spike sintering profile were employed to decrease the sintering temperature and reduce the grain size. The modified ceramic exhibits improved insulating properties and hence a higher breakdown strength, leading to a high recoverable energy density of 4.9 J/cm3 and a high energy efficiency of 88% at 430 kV/cm. The ceramic also exhibits satisfactory temperature stability over a wide temperature range from 25 to 125 °C and charge-discharge performance, making it a promising candidate for high-power dielectric energy storage applications.