The low ionic conductivity of solid-state electrolytes (SSEs) and the inferior interfacial reliability between SSEs and solid-state electrodes are two urgent challenges hindering the application of solid-state sodium batteries (SSSBs). Herein, sodium (Na) super ionic conductor (NASICON)-type SSEs with a nominal composition of Na_3+2xZr_2–xMg_xSi₂PO₁₂ were synthesized using a facile two-step solid-state method, among which Na_3.3Zr_1.85Mg_0.15Si₂PO₁₂ (x = 0.15, NZSP-Mg_0.15) showed the highest ionic conductivity of 3.54 mS∙cm^–1 at 25 °C. By means of a thorough investigation, it was verified that the composition of the grain boundary plays a crucial role in determining the total ionic conductivity of NASICON. Furthermore, due to a lack of examination in the literature regarding whether NASICON can provide enough anodic electrochemical stability to enable high-voltage SSSBs, we first adopted a high-voltage Na₃(VOPO₄)₂F (NVOPF) cathode to verify its compatibility with the optimized NZSP-Mg_0.15 SSE. By comparing the electrochemical performance of cells with different configurations (low-voltage cathode vs high-voltage cathode, liquid electrolytes vs SSEs), along with an X-ray photoelectron spectroscopy (XPS) evaluation of the after-cycled NZSP-Mg_0.15, it was demonstrated that the NASICON SSEs are not stable enough under high voltage, suggesting the importance of investigating the interface between the NASICON SSEs and high-voltage cathodes. Furthermore, by coating NZSP-Mg_0.15 NASICON powder onto a polyethylene (PE) separator (PE@NASICON), a 2.42 A∙h non-aqueous Na-ion cell of carbon|PE@NASICON|NaNi_2/9Cu_1/9Fe_1/3Mn_1/3O₂ was found to deliver an excellent cycling performance with an 88% capacity retention after 2000 cycles, thereby demonstrating the high reliability of a separator coated with NASICON-type SSEs.