Icing on structures represents a safety risk and has a significant economic impact on operational costs in areas such as aeronautics, power systems, marine vessels and platforms, and civil infrastructures. Non-wetting surfaces, because of their capability to repel water and to promote water drop mobility, have attracted increasing attention for their strong potential as anti-icing surfaces. A framework for understanding the behaviour of non-wetting (e.g. superhydrophobic) surfaces under icing conditions is provided. Icing of surfaces is a complex process requiring an understanding of interfacial fluid dynamics, phase-change thermodynamics, surface science, and material engineering. The desirable properties of ideal anti-icing surface(s) are identified, with the objective of defining how such a surface may be made. Combining classical nucleation theory with recent studies, we discuss the role of surface properties in the formation of ice on solid surfaces, focusing on the single and combined role of surface wetting and micro- and nanotexturing in different icing conditions. The capability of non-wetting surfaces to maintain liquid water repellency and mobility in icing conditions, instead of usual room temperature conditions, is also discussed, together with indications for reduced ice adhesion for such surfaces. The practical issue of durability is also briefly discussed.