Based on ab initio molecular dynamics simulations, we determined the melting curve of magnesium (Mg) up to ~460 GPa using the solid-liquid coexistence method. Between ~30 and 100 GPa, our melting curve is noticeably lower than those from static experiments, but is in good agreement with recent shock experiments. Up to ~450 GPa, our melting curve is generally consistent with the melting points from first-principles calculations using the small-cell coexistence method. We found that, at high pressures of a few hundred GPa, due to the strong softening of interatomic interactions in the liquid phase, solid-liquid coexistence simulations of Mg show some characteristics distinctively different from other metal systems, such as aluminum. For examp...