Conformational changes are essential for protein-protein and protein-ligand recognition. Here we probed changes in the structure of the protein ubiquitin at low temperatures in supercooled water using NMR spectroscopy. We demonstrate that ubiquitin is well folded down to 263 K, although slight rearrangements in the hydrophobic core occur. However, amide proton chemical shifts show non-linear temperature dependence in supercooled solution and backbone hydrogen bonds become weaker in the region that is most prone to cold-denaturation. Our data suggest that the weakening of the hydrogen bonds in the β-sheet of ubiquitin might be one of the first events that occur during cold-denaturation of ubiquitin. Interestingly, the same region is strongly involved in ubiquitin-protein complexes suggesting that this part of ubiquitin more easily adjusts to conformational changes required for complex formation.