A full account is given of our recent theoretical discovery [A. B. Belonoshko, R. Ahuja, and B. Johansson, Phys. Rev. Lett. 87, 165505 (2001)] of the fcc-bcc transition in Xe at high pressure and temperature. The interaction model and method for calculating phase boundaries are exhaustively tested by independent methods. The model was carefully checked against experimental data and results of ab initio molecular dynamics and it was found to perform very well. The two-phase method employed for finding the melting transition was compared with the robust thermodynamic approach and was found to provide data in exact agreement with the latter. The deviation of the calculated melting curve from the experimental one is quite tolerable at low pressures. After a reinterpretation of the experimental data, our results are also in good agreement with recent diamond anvil cell experiments. At a pressure of around 25 GPa and a temperature of about 2700 K, we find a triple fcc-bcc-liquid point. The fcc-bcc boundary is calculated without reference to the experimental data, in contrast to our previous work, and found to be in nice agreement with previous calculations as well as with the experimental data points, which, however, were interpreted as melting. Our finding concerning the fcc-bcc transition is confirmed by the direct molecular dynamics simulation of the fcc, bcc, and liquid phases in the same computational cell. In this simulation, it was observed that while the fcc phase melts, the bcc structure solidifies. Since Xe is a typical rare-gas solid, the fcc-bcc transition can now be expected for a number of other van der Waals systems, first of all in Ar and Kr. Our finding suggests, that the transition from close packed to bcc structure might be more common at high pressure and high temperature than was previously anticipated. The performed thorough test of methods and models in this study leads us to suggest that the original interpretation of experimental results is erroneous.