The freezing of water affects the processes that determine Earth’s climate, therefore, accurate weather and climate forecasts hinge on good predictions of ice nucleation rates. Such rate predictions are based on extrapolations using classical nucleation theory, which assumes that the structure of nanometer-sized ice crystallites corresponds to that of hexagonal ice, the thermodynamically stable form of bulk ice. However, simulations with various water models find that ice nucleated and grown under atmospheric temperatures is at all sizes stacking-disordered, consisting of random sequences of cubic and hexagonal ice layers. This implies that stacking- disordered ice crystallites either are more stable than hexagonal ice crystallites or form because of non-equilibrium dynamical effects, with both scenarios challenging central tenets of classical nucleation theory. Here we use rare-event sampling and free energy calculations with the mW water model to show that the entropy of mixing cubic and hexagonal layers makes stacking-disordered ice the stable phase for crystallites up to a size of at least 100,000 molecules. We find that stacking-disordered critical crystallites at 230 kelvin are about 14 kilojoules per mole of crystallite more stable than hexagonal crystallites, making their ice nucleation rates more than three orders of magnitude higher than predicted by classical nucleation theory. This effect on nucleation rates is temperature dependent, being the most pronounced at the warmest conditions, and should affect the modelling of cloud formation and ice particle numbers, which are very sensitive to the temperature dependence of ice nucleation rates. We conclude that classical nucleation theory needs to be corrected to include the dependence of the crystallization driving force on the size of the ice crystallite when interpreting and extrapolating ice nucleation rates from experimental laboratory conditions to the temperatures that occur in clouds.