We use nanoparticle-polymer composites to demonstrate the anti-icing capability of superhydrophobic surfaces and report direct experimental evidence that such surfaces are able to prevent ice formation upon impact of supercooled water both in laboratory conditions and in natural environments. We find that the anti-icing capability of these composites depends not only on their superhydrophobicity but also on the size of the particles exposed on the surface. The critical particle sizes that determine the superhydrophobicity and the anti-icing property are in two different length scales. The effect of particle size on ice formation is explained by using a classical heterogeneous nucleation theory. This result implies that the anti-icing property of a surface is not directly correlated with the superhydrophobicity, and thus, it is uncertain whether a superhydrophobic surface is anti-icing without detailed knowledge of the surface morphology. The result also opens up possibilities for rational design of anti-icing superhydrophobic surfaces by tuning surface textures in multiple length scales.