Phase diagrams of refractory metals remain essentially unknown. Moreover, there is an ongoing controversy over the high-pressure melting temperatures of these metals: results of diamond anvil cell (DAC) and shock wave experiments differ by at least a factor of 2. From an extensive ab initio study on tantalum we discovered that the body-centered cubic phase, its physical phase at ambient conditions, transforms to another solid phase, possibly hexagonal omega phase, at high temperature. Hence the sample motion observed in DAC experiments is very likely not due to melting but internal stresses accompanying a solid-solid transformation, and thermal stresses associated with laser heating.