Water freezing remains a perennial topic of great relevance to many important aspects of our lives; from the climate to human society and from economics to medicine, frozen water profoundly influences our living environment and life activities. There have been numerous publications on water freezing; however, confusion regarding the process of freezing remains. In this review, we mainly focused on the nucleation aspects of water freezing; in particular, we focused on the effect of the surface morphology and nanostructure of foreign bodies. This review covers the recent progress in ice nucleation and anti-freezing strategies within the framework of nucleation principles. In this regard, we first summarize the crystal nucleation theories. Due to high interfacial energy, ice crystallization is primarily controlled by heterogeneous nucleation events, because the homogeneous nucleation barrier of ice is extremely high. In addition to the interfacial energy, the interfacial morphology or nanostructure of foreign bodies plays a diverse role under different supercooling regimes due to the Gibbs–Thomson effect. This effect gives rise to the inverse homogeneous-like nucleation phenomenon, in which foreign bodies have little influence on the nucleation barrier. This ensures the accurate measurement of the nucleation barrier, critical size, and water–ice interfacial energy, in agreement with the latest studies based on a microemulsions approach, metadynamics, the mW model, etc. As a consequence, anti-freezing strategies can be implemented by reducing the nucleation rate through restriction of the contact area of the water/substrate interface, by increasing the heterogeneous nucleation barrier through modification of the interfacial properties of foreign particles, including the interfacial structure and the interaction between the water and foreign particles and by kink kinetics. Within this context, the anti-freezing mechanism of superhydrophobic substrates was reviewed. Therefore, it follows that by significantly reducing the contact area between the water and substrate, superhydrophobic materials can effectively reduce the heterogeneous nucleation rate. We hope that this review will provide a unified picture and guidance for future work on water freezing.