Na-ion battery, as an alternative high-efficiency and low-cost energy storage device to Li-ion battery, has attracted wide interest for electrical grid and vehicle applications. However, demonstration of a full-cell battery with high energy and long cycle life remains a significant challenge. Here, we investigated the role of solid electrolyte interphase (SEI) formation on both cathodes and anodes and revealed a potential way to achieve long-term stability for Na-ion battery full-cells. Pre-cycling of cathodes and anodes leads to preformation of SEI, and hence mitigates the consumption of Na ions in full-cells. The example full-cell of Na0.44MnO2-hard carbon with pre-cycled and capacity-matched electrodes can deliver a specific capacity of ~116mAh/g based on Na0.44MnO2 at 1C rate (1C=120mA/g). The corresponding specific energy is ~313Wh/kg based on the cathode. Excellent cycling stability with ~77% capacity retention over 2000 cycles was demonstrated at 2C rate. Our work represents a leap forward in Na-ion battery development.