Heterogeneous nucleation of ice induced by organic materials is of fundamental importance for climate, biology, and industry. Among organic ice-nucleating surfaces, monolayers of long chain alcohols are particularly effective, while monolayers of fatty acids are significantly less so. As these monolayers expose to water hydroxyl groups with an order that resembles the one in the basal plane of ice, it was proposed that lattice matching between ice and the surface controls their ice nucleating efficiency. Organic monolayers are soft materials and display significant fluctuations. It has been conjectured that these fluctuations assist in the nucleation of ice. Here we use molecular dynamic simulations and laboratory experiments to investigate the relationship between the structure and fluctuations of hydroxylated organic surfaces and the temperature at which they nucleate ice. We find that these surfaces order interfacial water to form domains with ice-like order that are the birthplace of ice. Both mismatch and fluctuations decrease the size of the preordered domains and monotonously decrease the ice freezing temperature. The simulations indicate that fluctuations depress the freezing efficiency of monolayers of alcohols or acids to half the value predicted from lattice mismatch alone. The model captures the experimental trend in freezing efficiencies as a function of chain length and predicts that alcohols have higher freezing efficiency than acids of the same chain length. These trends are mostly controlled by the modulation of the structural mismatch to ice. We use classical nucleation theory to show that the freezing efficiencies of the monolayers are directly related to their free energy of binding to ice. This study provides a general framework to relate the equilibrium thermodynamics of ice binding to a surface and the nonequilibrium ice freezing temperature and suggests that these could be predicted from the structure of interfacial water.