Ice accretion on external aircraft surfaces due to the impact of supercooled water droplets can negatively affect the aerodynamic performance and reduce the operational capability and, therefore, must be prevented. Icephobic coatings capable of reducing the adhesion strength of ice to a surface represent a promising technology to support thermal or mechanical ice protection systems. Icephobicity is similar to hydrophobicity in several aspects and superhydrophobic surfaces embody a straightforward solution to the ice adhesion problem. Short/ultrashort pulsed laser surface treatments are proposed as a viable technology to generate superhydrophobic properties on metallic surfaces. However, it has not yet been verified whether such surfaces are generally icephobic under representative icing conditions. This study investigates the ice adhesion strength on Ti6Al4V, an alloy commonly used for aerospace components, textured by means of direct laser writing, direct laser interference patterning, and laser-induced periodic surface structures laser sources with pulse durations ranging from nano- to femtosecond regimes. A clear relation between the spatial period, the surface microstructure depth, and the ice adhesion strength under different icing conditions is investigated. From these observations, a set of design rules can be defined for superhydrophobic surfaces that are icephobic, too.