The Gibbs free energies of bcc and fcc Mo are calculated from first principles in the quasiharmonic approximation in the pressure range from 350 to 850 GPa at room temperatures up to 7500 K. It is found that Mo, stable in the bcc phase at low temperatures, has lower free energy in the fcc structure than in the bcc phase at elevated temperatures. Our density-functional-theory-based molecular dynamics simulations demonstrate that fcc melts at higher than bcc temperatures above 1.5 Mbar. Our calculated melting temperatures and bcc-fcc boundary are consistent with the Mo Hugoniot sound speed measurements. We find that melting occurs at temperatures significantly above the bcc-fcc boundary. This suggests an explanation of the recent diamond anvil cell experiments, which find a phase boundary in the vicinity of our extrapolated bcc-fcc boundary.