Sustainable batteries using nontoxic, earth-abundant, and low-cost materials are key to decarbonization. Olivine NaFePO4 fulfills these criteria, is attractive for Na-ion batteries, and can be derived from LiFePO4 recycled from Li-ion battery wastes. Critical knowledge is needed for transforming LiFePO4 to NaFePO4 to enable such a sustainable, green engineering path toward high-performance Na-ion batteries. Herein, we report on the development of a stable-cycling, sustainable olivine iron phosphate-based Na-ion battery empowered by an improved understanding of materials transformation and electrolyte chemistry. First, we found that the conventional carbonate electrolyte with fluoroethylene carbonate additive causes an additional plateau (∼2.4 V) at the end of the discharge process of the FePO4||Na metal cell, leading to lower initial discharge capacity and voltage. This result shows that the voltage profile is influenced by not only intrinsic materials phase transformation during battery cycling but also the electrolyte additives and interphases formed. With the 1 M NaPF6 diglyme electrolyte, we achieved an excellent capacity retention of 96% and 98% after 500 cycles at 1 and 5 C, respectively. Second, we chemically sodiated FePO4 to form single-phase Na0.9FePO4. Na0.9FePO4||hard carbon full cells demonstrated a remarkable capacity retention of ∼84% at 3 and 5 C after 1000 cycles. The successful implementation of hard carbon, which can be derived from biomass waste, will further improve the sustainability of energy storage technologies. Our research demonstrates that electrolyte chemistry influences the voltage profile of phase-changing electrodes and provides effective electrolyte and full-cell design solutions for stable-cycling NaFePO4.