A high Mg2+ ion-conducting phosphate-based solid electrolyte with a solid solution form was synthesized by substituting the tetravalent Zr4+ site in MgZr4P6O24 for a pentavalent Nb5+. Because of the replacement, the activation energy for Mg2+ ion migration became considerably low compared with that for the mother phase of MgZr4P6O24 and an appreciable enhancement of Mg2+ ion conductivity was observed especially in a relatively low-temperature region. The Zr4+ site substitution in MgZr4P6O24 for Nb5+ makes for a superior effect on the stabilization of the high-temperature phase of MgZr4P6O24. A successful formation of the above mentioned solid solution results in the statistical distribution of mobile Mg2+ ion in three sites occupied by mobile Mg2+ and contributes greatly to making a smooth Mg2+ ion migration in the solid solution.