Laser surface texturing (LST) has been demonstrated to be an effective method to induce the icephobic characteristics on metallic surfaces, which can be exploited for several applications including aerospace, energy, and communication. Using femtosecond (fs) lasers, highly-repeatable multiscale surface topographies comprised of microscale patterns and self-organized micro/nanoscale features such as laser-induced periodic surface structures (LIPSS) can be fabricated. This study investigated the influence of multi-scale surface textures produced on aluminum plates by fs-LST on the anti-icing performance. Firstly, surface features with different morphologies were fabricated by varying the fs-LST process parameters such as hatch spacing, scanning speed and the number of scanning passes. Surface topography of the textures was characterized using optical profilometry and scanning electron microscopy whereas Energy Dispersive Spectroscopy was used for analyzing the chemical composition. The wettability of the surfaces was studied using static, advancing and receding contact angle measurements. Further, icephobicity evaluation was carried out using two main techniques:  i) by measuring the freezing time delay using an optical goniometer equipped with a subzero Peltier cell and, ii) by measuring the ice adhesion strength using an ice adhesion set-up based on horizontal shear stress application. Icing analysis and ice adhesion tests indicated that optimal microscale patterns overlapped with LIPSS features effectively increase the freezing time, mostly through the existence of the Cassie-Baxter regime at the interface between ice and textured surface, with a beneficial reduction in the ice adhesion strength. These results highlight that surface texturing by fs lasers is effective in achieving icephobic surfaces.