The ice accumulation on solid surfaces in low temperature environments seriously affects the operating efficiency and safety of outdoor equipment, such as aerospace, wind turbine, power line, etc. In recent years, a new passive anti-icing method based on superhydrophobic materials has attracted wide attention. The superhydrophobicity is generally achieved through constructing mirco/nano structures of low surface energy. On a superhydrophobic surface, a sessile water droplet has a high contact angle and a low roll-off angle. An impacting droplet could also bounce off the non-wetting surface over a certain Weber number range. The rough structures on a superhydrophobic surface reduce the interfacial heat transfer efficiency, which suppresses the nucleation of ice. The low surface energy may also benefit the removal of ice from the surface, once the icing has occurred. Therefore, the superhydrophobic surfaces show a broad application prospect in the field of anti/de-icing technology because of the excellent water repellency, ice nucleation inhibition, and ice adhesion strength reduction. As a non-traditional technique, laser processing shows high efficiency in fabricating micro/nano structures on solid surfaces. Therefore, laser processing has become an effective method to prepare superhydrophobic surfaces, and has been further used to study the anti-icing performance of the fabricated surfaces. In this review, the wetting theory and the icing mechanism of water droplets on solid surfaces were firstly summarized. Then, the anti-icing performance of laser-processed superhydrophobic surfaces was evaluated comprehensively, including icing delay time of sessile water droplets, accumulation of dynamic droplets, ice adhesion strength, frost delay or anti-frost, as well as surface ice accumulation and deicing. The droplet icing delay time was affected by the nucleation rate and the heat transfer rate at the interface, while the droplet accumulation was closely related to surface wettability. The ice adhesion strength reflected the adhesion of ice on the superhydrophobic surfaces and the difficulty of deicing. Superhydrophobic surfaces had a significant capacity to delay icing, but the performance of the surfaces might become weak or even failed under low temperature and high humidity conditions. In addition, the deicing process might also damage the microstructures of the superhydrophobic surfaces, which in turn reduced their anti-icing properties. Finally, the future research direction for the laser processing of superhydrophobic surfaces and the anti-icing performance was prospected.