The development of electrolytes with high ionic conductivity and stable electrode–electrolyte interfaces is crucial for the practical realization of solid-state sodium batteries. In this study, the effect of heteroatom doping in a von-Alpen-type Na super ionic conductor (NASICON) was investigated by substituting Zr⁴⁺ with Mg²⁺, Zn²⁺, and La³⁺ to enhance its material properties and evaluate its potential for solid-state sodium battery applications. Computational chemistry was employed to predict the thermodynamic stability influenced by dopant introduction and the changes in ionic conductivity arising from crystal structure distortion, with the predictions validated by experiments. The optimized Zn²⁺-doped NASICON (Zn-NZSP0.07) exhibited the highest total ionic conductivity of 2.74×10⁻³ S∙cm⁻¹, representing a 4.5-fold increase compared with undoped NASICON (6.00×10⁻⁴ S∙cm⁻¹). The material also showed a high relative density of 99.1%, indicating a compact and well-sintered microstructure, as confirmed by a three-point bending test. Furthermore, a high critical current density of 1.4 mA∙cm⁻² was achieved in symmetric cell testing. Additionally, a Na₃V₂(PO₄)₃||Zn-NZSP0.07||Na cell delivered an initial capacity of 103.9 mAh∙g⁻¹ at 0.1 A∙g⁻¹ and retained 73.4% of its capacity after 200 cycles. These results demonstrate that optimal heteroatom doping is crucial for enhancing the performance of NASICON.