Iron (Fe)-based layered oxide cathodes that employ Fe3+/Fe4+ redox reaction present a family of attractive cathode materials for sodium-ion batteries as iron is abundant, low-cost, and environmentally benign. However, their electrochemical performance is not yet satisfactory and requires further improvement. In this study, we investigate the effect of electrolytes on the electrochemical performance of α-NaFeO2, a prototypical model of Fe-based layered cathodes. First, we established the critical impact of the poor cathode-electrolyte interfacial stability on cell performances. Systematic electrochemical tests and material characterizations further revealed the degradation mechanism in which the highly reactive Fe4+ state in the charged Na1−xFeO2 electrodes promotes severe electrolyte decomposition and subsequent growth of a thick interface layer that leads to impedance rise and performance degradation. In addition, the superior performance of NaPF6 over NaClO4 and the beneficial effect of the FEC additive are reported.