We have presented a detailed investigation of the effects of Mg substitution on the structure, electrochemical performance and Na-ion diffusion in high voltage P2-type Na2/3Ni1/3-xMgxMn2/3O2 (0 <x< 0.20) cathode materials for Na-ion batteries. Structural analysis using neutron diffraction showed that Mg2+ substitutes random Ni2+ on the 2b sites from ordered [(Ni2+/Mn4+)O6] honeycomb units along the ab-plane, leading to an AB-type structure that can be indexed using the P63 space group. Within the sodium layers, high Mg-substituting levels (i.e. x = 0.2) caused a disruption in the typical Na zig-zag ordering observed in the undoped material, leading to a more disordered Na distribution in the layers. Load curves of the x = 0.1, 0.2 materials show smooth electrochemistry, indicative of a solid-solution process. Furthermore, DFT calculations showed an increase on Na-ion diffusivity on the Mg-substituted samples. Enhanced cycling stability was also observed in these materials; structural analysis using high-resolution in-operando synchrotron X-ray diffraction show that such an improved electrochemical performance is caused by the suppression of the O2 phase and switch to the formation of an OP4 phase. Ab-initio studies support our experimental evidence showing that the OP4 phase (cf. O2) is the most thermodynamically stable phase at high voltages for Mg-substituted compounds. Finally, we have provided evidence using diffraction for the x = 1/2 and x = 1/3 intermediate Na+-vacancy ordered phases in P2-Na 2/3Ni1/3Mn2/3O2.