As a ubiquitous natural phenomenon, ice/frost formation on solid surfaces have adverse effects on many commercial and residential activities. Icephobic surfaces feature low ice adhesion strengths (< 100 kPa) can passively retard ice formation and ease ice removal. Superhydrophobic surfaces and liquid-lubricating surfaces are two prevailing categories of icephobic surfaces. However, their long-term stability is relatively poor, and the ice adhesion strengths are not low enough for passive removal of small ice crystals (e.g., frosts) from the surfaces. Herein, we combine the superhydrophobic and liquid-like properties in one surface to obtain durable icephobic surfaces with extremely low ice adhesion strengths (about 0.035 kPa). Ices and frosts can be removed from the surface under the action of gravity or gas purge. These surfaces are prepared based on surface nanoconical structure and covalently-grafted liquid-like perfluorinated polyether (PFPE) coating, which show synergy effects on suppressing icing and frosting by promoting expulsion of subcooled condensate droplets from the nanotexture and decreasing ice adhesion strengths. The icephobic surfaces show significantly better durability compared to lubricant-impregnated textured surfaces. Our results provide a new avenue to design passive anti-icing/anti-frosting surfaces for a wide range of applications where surfaces are exposed to humid and low-temperature environments.