Ice-nucleating proteins (INPs) found in bacteria are the most effective ice nucleators known, enabling the crystallization of water at temperatures close to 0 °C. Although their function has been known for decades, the underlying mechanism is still under debate. Here, we show that INPs from Pseudomonas syringae in aqueous solution exhibit a defined solution structure and show no significant conformational changes upon cooling. In contrast, irreversible structural changes are observed upon heating to temperatures exceeding ∼55 °C, leading to a loss of the ice-nucleation activity. Sum-frequency generation (SFG) spectroscopy reveals that active and heat-inactivated INPs impose similar structural ordering of interfacial water molecules upon cooling. Our results demonstrate that increased water ordering is not sufficient to explain INPs' high ice-nucleation activity and confirm that intact three-dimensional protein structures are critical for bacterial ice nucleation, supporting a mechanism that depends on the INPs' supramolecular interactions.