Dielectric energy-storage capacitors have received increasing attention in recent years due to the advantages of high voltage, high power density, and fast charge/discharge rates. Here, a new environment-friendly 0.76NaNbO3–0.24(Bi0.5Na0.5)TiO3 relaxor antiferroelectric (AFE) bulk ceramic is studied, where local orthorhombic Pnma symmetry (R phase) and nanodomains are observed based on high-resolution transmission electron microscopy, selected area electron diffraction, and in/ex situ synchrotron X-ray diffraction. The orthorhombic AFE R phase and relaxor characteristics synergistically contribute to the record-high energy-storage density Wrecof ≈12.2 J cm−3 and acceptable energy efficiency η≈ 69% at 68 kV mm−1, showing great advantages over currently reported bulk dielectric ceramics. In comparison with normal AFEs, the existence of large random fields in the relaxor AFE matrix and intrinsically high breakdown strength of NaNbO3-based compositions are thought to be responsible for the observed energy-storage performances. Together with the good thermal stability of Wrec (>7.4 J cm−3) and η (>73%) values at 45 kV mm−1 up to temperature of 200 °C, it is demonstrated that NaNbO3-based relaxor AFE ceramics will be potential lead-free dielectric materials for next-generation pulsed power capacitor applications.