Organisms that thrive at cold temperatures produce ice-binding proteins to manage the nucleation and growth of ice. Bacterial ice-nucleating proteins (INP) are typically large and form aggregates in the cell membrane, while insect hyperactive antifreeze proteins (AFP) are soluble and generally small. Experiments indicate that larger ice-binding proteins and their aggregates nucleate ice at warmer temperatures. Nevertheless, a quantitative understanding of how size and aggregation of ice-binding proteins determine the temperature Thet at which proteins nucleate ice is still lacking. Here, we address this question using molecular simulations and nucleation theory. The simulations indicate that the 2.5 nm long antifreeze protein TmAFP nucleates ice at 2 ± 1 °C above the homogeneous nucleation temperature, in good agreement with recent experiments. We predict that the addition of ice-binding loops to TmAFP increases Thet, but not enough to compete in efficiency with the bacterial INP. We implement an accurate procedure to determine Thet of surfaces of finite size using classical nucleation theory, and, after validating the theory against Thet of the proteins in molecular simulations, we use it to predict Thet of the INP of Ps. syringae as a function of the length and number of proteins in the aggregates. We conclude that assemblies with at most 34 INP already reach the Thet = -2 °C characteristic of this bacterium. Interestingly, we find that Thet is a strongly varying nonmonotonic function of the distance between proteins in the aggregates. This indicates that, to achieve maximum freezing efficiency, bacteria must exert exquisite, subangstrom control of the distance between INP in their membrane.