NASICON (sodium (Na) superionic conductor) compounds have attracted considerable attention as promising solid electrolyte materials for advanced Na-based batteries. In this study, we investigated the improvement in ionic conductivities of von-Alpen-type NASICON (vA-NASICON) ceramic electrolytes by introducing a magnesium ion (Mg²⁺) as a heterogeneous element. The optimal Mg-doped vA-NASICON exhibited a high ionic conductivity of 3.64×10⁻³ S·cm⁻¹, which was almost 80% higher than that of un-doped vA-NASICON. The changes in physicochemical properties of the vA-NASICONs through the Mg introduction were systematically analyzed, and their effects on the ionic conductivities of the vA-NASICON were studied in detail. When the optimal ratio of Mg²⁺ was used in a synthetic process, the relative density (96.6%) and grain boundary ionic conductivity (σ_gb) were maximized, which improved the total ionic conductivity (σ_t) of the vA-NASICON. However, when Mg²⁺ was introduced in excess, the ionic conductivity decreased because of the formation of an undesired sodium magnesium phosphate (Na_xMg_yPO₄) secondary phase. The results of this study are expected to be effectively applied in the development of advanced sodium-based solid electrolytes with high ionic conductivities.