Ice-building up on the leading edge of wings and other surfaces exposed to icing atmospheric conditions can negatively influence the aerodynamic performances of aircrafts. In the past, research activities focused on understanding icing phenomena and finding effective countermeasures. Efforts have been dedicated to creating coatings capable of reducing the adhesion strength of ice to a surface. Nevertheless, coatings still lack functional stability, and their application can be harmful to health and the environment. Pulsed laser surface treatments have been proven as a viable technology to induce icephobicity on metallic surfaces. However, a study aimed to find the most effective microstructures for reducing ice adhesion still needs to be carried out. This study investigates the variation of the ice adhesion strength of micro-textured aluminum surfaces treated using laser-based methods. The icephobic performance is tested in an icing wind tunnel, simulating realistic icing conditions. Finally, it is shown that optimum surface textures lead to a reduction of the ice adhesion strength from originally 57 kPa down to 6 kPa, corresponding to a relative reduction of similar to 90%. Consequently, these new insights will be of great importance in the development of functionalized surfaces, permitting an innovative approach to prevent the icing of aluminum components.