The function of critical biological materials, such as proteins, is intrinsically tied to their structure, and this structure is in turn heavily dependent on the properties of the solvent, most commonly water or dilute aqueous solutions. As water is known to exhibit anomalous properties, especially at supercooled temperatures, it is natural to ask how these properties might impact the thermodynamics of protein folding. To investigate this question, we use molecular simulation to explore the behavior of a model miniprotein, Trp-cage, as low as 70 K below the freezing point of the solvent at ambient pressure. Surprisingly, we find that while the expected cold denaturation of the protein is observed at moderate supercooling, further cooling to more than 55 K below the freezing point leads to cold refolding of the protein. Structural and hydrogen bonding analysis suggests that this refolding is driven by the desolvation of the protein's hydrophobic core, likely related to the pronounced decrease in density at this temperature. Beyond their intrinsic fundamental interest, these results have implications for cryomicroscopy and cryopreservation, where biological materials are often transiently subjected to these extreme conditions.