Icing of surfaces is commonplace in nature, technology and everyday life, bringing with it sometimes catastrophic consequences. A rational methodology for designing materials with extraordinary resistance to ice formation and adhesion remains however elusive. We show that ultrafine roughnesses can be fabricated, so that the ice nucleation-promoting effect of nanopits on surfaces is effectively counteracted in the presence of an interfacial quasiliquid layer. The ensuing interface confinement strongly suppresses the stable formation of ice nuclei. We explain why such nanostructuring leads to the same extremely low, robust nucleation temperature of ∼-24 °C for over three orders of magnitude change in RMS size (∼0.1 to ∼100 nm). Overlaying such roughnesses on pillar-microtextures harvests the additional benefits of liquid repellency and low ice adhesion. When tested at a temperature of -21 °C, such surfaces delayed the freezing of a sessile supercooled water droplet at the same temperature by a remarkable 25 hours.