Tetragonal and cubic phase Na3PS4 sodium electrolytes were successfully prepared by a relatively low rotation speed mechanical milling (400 rpm) route, aiming at homogeneous materials. The influence of the mechanical milling and annealing on the structure and ionic conductivity are studied by XRD and impedance spectroscopy, giving insight into the optimal mechanical synthesis conditions. Fourier analysis of the XRD data, compared to DFT based MD simulations reflects the diffusion pathway, where the simulations indicate a vacancy induced high bulk Na-ion mobility in both cubic and tetragonal phases. 23Na solid-state NMR relaxation experiments were applied to investigate the Na-ion bulk diffusion in both the cubic and tetragonal phases, showing reasonable agreement with the MD simulation results. The MD simulations indicate that the bulk mobility of both phases may be further improved by introducing more Na vacancies. The macroscopic ionic conductivity probed by impedance spectroscopy is much smaller than that predicted by the bulk Na-ion mobility, in particular for the tetragonal phase, suggesting a large impact of amorphous phase fractions and/or grain boundaries on the macroscopic Na-ion conductivity. In particular in the less crystalline cubic phase, the amorphous fraction present as a consequence of the lower annealing temperature suggests that this phase may lead to a decrease in grain boundary resistance, which may be further exploited to improve the performance of all solid state Na-ion batteries with the Na3PS4 solid electrolyte.