The phase diagram of solid oxygen at terapascal pressures and several thousand Kelvin has been studied with ab initio density functional theory within the quasiharmonic approximation for the vibrational free energy. Our work extends previous theoretical studies done at zero temperature and shows that temperature has a dramatic effect on the sequence of phases. At low temperature, the transition from onefold (molecular) to fourfold coordination takes place through two intermediate phases with twofold coordination and space groups $I{4}_{1}/acd$ and $Cmcm$. Above 8000 K we find that these two intermediate phases are no longer stable, and oxygen transforms directly from a molecular phase to a fourfold coordinated phase of space group $Fmmm$. We also find that the transition between $Cmcm$ and $Fmmm$ can be ascribed as a second-order transition driven by an electronic instability.