In this work, an anti-icing structured surface was fabricated by combining laser ablation with hydrothermal treatment. A micro-patterned surface on a Ti alloy (TC4) substrate was easily fabricated by a highly effective nanosecond pulsed laser ablation. It was observed that titania (TiO2) nanostructures were formed by hydrothermal treatment in aqueous alkali on the laser ablated TC4 substrate to obtain the micro/nano-hierarchical structures. The growth mechanism of the tunable nanoarrays was discussed by the adjustment of hydrothermal temperature. The as-prepared samples exhibited excellent superhydrophobicity with contact angles greater than 160°. It was found that optimized hydrothermal treatment on laser-processed TC4 substrates could further enhance surface anti-icing property. The results showed that the delay time (DT) had been extended by achieving over 90 min for the water droplets to freeze on the as-prepared structured surfaces, providing great potential in various anti-icing applications.