Conventional methods to calculate the thermodynamics of crystals evaluate the harmonic phonon spectra and therefore do not work in frequent and important situations where the crystal structure is unstable in the harmonic approximation, such as the body-centered cubic (bcc) crystal structure when it appears as a high-temperature phase of many metals. A method for calculating temperature dependent phonon spectra self consistently from first principles has been developed to address this issue. The method combines concepts from Borns inter-atomic self-consistent phonon approach with first principles calculations of accurate inter-atomic forces in a super-cell. The method has been tested on the high temperature bcc phase of Ti, Zr and Hf, as representative examples, and is found to reproduce the observed high temperature phonon frequencies with good accuracy.