Ice build-up and adhesion of snow on surfaces can be a serious problem in many fields such as power lines, telecommunications, wind turbines and power generation. Super-hydrophobic (SHP) surfaces exhibit anti-icing properties only in some cases; a relationship between SHP and ice-phobicity has yet to be clearly understood, and the durability of the ice-phobic properties of these surfaces is still an open question. It is well known that surfaces structured hierarchically, composed of a micrometer structure, an overlapping nanometer structure and low-energy molecules, exhibit SHP properties. In this study, we present an easy, fast, and inexpensive process for obtaining super-hydrophobic hierarchical aluminum surfaces with durable anti-icing properties. The three-step process consists of mechanical surface treatments (sandblasting, tumbling, etc.) to impart microroughness, growing a nanostructured pseudo-boehmite AlOOH by hydrothermal treatment, and eventually applying a fluoroalkylsilane (FAS)-based coating. Different samples were prepared using different microroughness treatments. We conducted a morphological study, comprehensive characterization of hydrophobic properties at both room temperature and low temperature, and shear stress tests, and this revealed important differences between the samples. In particular, it is shown that microroughness can influence the superhydrophobic and anti-icing behavior of the surfaces. Promising results were found for sandblasted specimens, especially in terms of anti-icing properties and durability: low ice adhesion values are maintained even after 20 shear stress tests.