Icing on aircraft surfaces during operation poses a threat to flight safety. As a passive anti-icing technology, hydrophobic microstructure can achieve long-term anti-icing. In this work, a composite process combining hot-embossing of PVD-coated punches with a low surface energy fluoride-modification scheme is proposed to generate nanoscale cluster structures on hundreds of microns array channels to construct a superhydrophobic micro-nano composite structure. The droplet freezing and frosting behavior of the hydrophobic microstructures was analyzed, and it was found that the anti-icing and anti-frost properties of the microstructure surface improved with an increase in the microstructure period size (T). Compared with the original surface, the freezing time of the microstructure at T = 500 μm was delayed by 214.3% (7 s → 22 s), and the frost layer coverage time was delayed by 75.7% (70 s → 123 s). The maximum water contact angle of the superhydrophobic micro-nano composite structure was 153.3°, and the droplet freezing time was delayed to 95 s, which is a 1166.67% difference, indicating that the multi-stage micro-nano composite structure can significantly improve surface anti-icing performance. The main reason for this result is that the bottom of the microstructure can store air pockets, preventing droplet wetting and heat exchange.