Solid electrolyte materials exhibiting high Mg-ion conductivity are required to develop Mg-ion batteries. In this study, we focused on a Mg-ion-conducting solid phosphate based electrolyte, MgZr4(PO4)(6) (MZP), and evaluated the ionic conductivity of NASICON-type and -iron sulfate-type MgZr4(PO4)(6) structures via density functional theory calculations. The calculations suggest that the migration energy of Mg is 0.63 eV for the NASICON-type structure and 0.71 eV for the -iron sulfate-type one, and the NASICON-type structure has higher ion conductivity. Although the NASICON-type MZP structure has not been experimentally realised, there is only an energy difference of 14 meV per atom with respect to that of the -iron sulfate-type structure. Therefore, in order to develop a synthesis method for the NASICON-type structure, we investigated pressure- and temperature-dependent variations in the free energy of formation using density functional perturbation theory calculations. The results suggest that the formation of the NASICON-type structure is disfavoured under the 0-2000 K and 0-20 GPa conditions.