Through a series of high-pressure x-ray diffraction experiments combined with in situ laser heating, we explore the pressure-temperature phase diagram of germanium (Ge) at pressures up to 110 GPa and temperatures exceeding 3000 K. In the pressure range of 64-90 GPa, we observe orthorhombic Ge-IV transforming above 1500 K to a previously unobserved high-temperature phase, which we denote as Ge-VIII. This high-temperature phase is characterized by a tetragonal crystal structure, space group I4/mmm. Density functional theory simulations confirm that Ge-IV becomes unstable at high temperatures and that Ge-VIII is highly competitive and dynamically stable at these conditions. The existence of Ge-VIII has profound implications for the pressure-temperature phase diagram, with melting conditions increasing to much higher temperatures than previous extrapolations would imply.