The melting curve of the body-centered cubic (bcc) phase of Mo has been determined for a wide pressure range using both direct ab initio molecular dynamics simulations of melting as well as a phenomenological theory of melting. These two methods show very good agreement. The simulations are based on density functional theory within the generalized gradient approximation. Our calculated equation of state of bcc Mo is in excellent agreement with experimental data. However, our melting curve is substantially higher than the one determined in diamond anvil cell experiments up to a pressure of 100 GPa. An explanation is suggested for this discrepancy.