Ice buildup can cause a major problems in many disparate fields, from airplanes to electrical transmission lines. Super-hydrophobic (SHP) surfaces may have potential anti-ice application due to their extreme water repellency. However, there is something lacking in the characterization of the ice behavior of these surfaces. Furthermore, durability is a major concern for this type of coatings. One class of super-hydrophobic surfaces consists of hierarchical structures, where a micrometer roughness is combined with a nanometer roughness and finally covered by a low-energy chemical finish. In the present work, we investigated experimentally the influence of the micrometric roughness of the surface of the aluminum alloy on the hierarchical micronano-structure and the consequent hydrophobic and antifreeze properties, especially in terms of durability. The aluminum alloy samples were sandblasted or polished to generate a different micrometer roughness. The following steps to obtain a super-hydrophobic hierarchical structure (nano-roughness and final low-energy chemical treatment) were kept constant for all samples. The hydrophobic properties were characterized at room and low temperatures and the anti-icing behavior was measured with shear stress tests. Several repetitions of shear stress measurement on the same samples and ice thawing cycles were performed to study the durability of the coatings. This work describes an easy, fast and affordable process to obtain super-hydrophobic materials with long-lasting anti-ice properties, with interesting applications in many industrial fields.