Fabricating and developing superhydrophobic anti-icing surfaces have been a research hotspot for eliminating undesired icing issues. Among various fabricating strategies, ultrafast laser micro-nano fabrication is regarded as a greatly promising technique owing to its advantages of high geometric accuracy, highly flexible microstructure or dimension availability, no contact, and no material limitation. A number of diverse micro-nanostructured superhydrophobic surfaces have been developed by ultrafast lasers and demonstrated extraordinary anti-icing properties. They are collectively known as ultrafast laser-fabricated superhydrophobic anti-icing surfaces (ULSASs). In this article, we reviewed the recent advances in ULSASs from micro-nano structure fabricating to anti-icing performances and to potential applications. The surface wettability and mechanisms of ultrafast laser micro-nano fabrication are first introduced, showing the strong ability of ultrafast laser for fabricating superhydrophobic surfaces. Then the deepened understanding of the relationship between superhydrophobicity and icephobicity is discussed in detail, including Cassie–Baxter stability, surface durability and environmental adaptability. Eventually, the passive anti-icing technique, the passive/active combined anti-icing technique and their practical applications are presented together with current challenges and future prospects.