Using a membrane-driven diamond anvil cell and both ac magnetic susceptibility and electrical resistivity measurements, we have characterized the superconducting phase diagram of elemental barium to pressures as high as 65 GPa. We have determined the superconducting properties of the recently discovered Ba-VI crystal structure, which can only be accessed via the application of pressure at low temperature. We find that Ba-VI exhibits a maximum Tc near 8 K, which is substantially higher than the maximum Tc found when pressure is applied at room temperature. We discuss our results in terms of the implications for pressure-induced superconductivity in other elements exhibiting complex/modulated structures at high pressure. Finally, we highlight the potential of cryogenic compression to reveal additional richness in previously explored high-pressure phase diagrams.