A novel superhydrophobic coating composed of soft polydimethylsiloxane microspheres and stiff SiO2 nanoparticles was developed and prepared. This superhydrophobic coating showed excellent superhydrophobicity with a large water contact angle of 171.3° and also exhibited good anti-icing performance and ultralow icing adhesion of 1.53 kPa. Furthermore, the superhydrophobic coating displayed good icing/deicing cycle stability, in which the icing adhesion was still less than 10.0 kPa after 25 cycles. This excellent comprehensive performance is attributed to stress-localization between ice and the surface, resulting from the synergistic effect of soft and stiff particles. This work thus opens a new avenue to simultaneously optimize the anti-icing and icephobic performance of a superhydrophobic surface for various applications.