The phase diagram of magnesium has been investigated to 211 GPa at 300 K, and to 105 GPa at 4500 K, by using a combination of x-ray diffraction and resistive and laser heating. The ambient pressure hcp structure is found to start transforming to the bcc structure at ∼45 GPa, with a large region of phase-coexistence that becomes smaller at higher temperatures. The bcc phase is stable to the highest pressures reached. The hcp-bcc phase boundary has been studied on both compression and decompression, and its slope is found to be negative and steeper than calculations have previously predicted. The laser-heating studies extend the melting curve of magnesium to 105 GPa and suggest that, at the highest pressures, the melting temperature increases more rapidly with pressure than previously reported. Finally, we observe some evidence of a new phase in the region of 10 GPa and 1200 K, where previous studies have reported a double-hexagonal-close-packed (dhcp) phase. However, the additional diffraction peaks we observe cannot be accounted for by the dhcp phase alone.