Lead-free relaxor ferroelectric ceramics with ultrahigh energy-storage performance are vital for pulsed power systems. We herein propose a strategy of phase and band structure engineering for high-performance energy storage. To demonstrate the effectiveness of this strategy, (1 - x)(0.75Na0.5Bi0.5TiO3-0.25SrTiO3)-xCaTi0.875Nb0.1O3(NBT-ST-xCTN, x = 0.1, 0.2, 0.3, 0.4, and 0.5) samples were designed and fabricated via the solid-state reaction method. The linear dielectric CTN was used as a modulator to tune both phase and band structures of the tested system. Our results show that both rhombohedral phase (R-phase) and tetragonal phase (T-phase) coexist in the samples. The R/T ratio decreases, while the band gap increases with increasing CTN content. The best energy-storage properties with large energy storage density (Wrec= 7.13 J/cm3), a high efficiency (η = 90.3%), and an ultrafast discharge time (25 ns) were achieved in the NBT-ST-0.4CTN sample with R/T = 0.121. Importantly, along with its excellent energy-storage performance, the sample exhibited superior thermal stability with the variations of Wrec≤ 7% and η ≤ 10% over the wide temperature range of 233-413 K. This work suggests that this engineering of phase and band structures is a promising strategy to achieve superior energy-storage properties in lead-free ceramics.