Ice formation and accumulation on surfaces can result in severe problems for solar photovoltaic installations, offshore oil platforms, wind turbines and aircrafts. In addition, blockage of pipelines by formation and accumulation of clathrate hydrates of natural gases has safety and economical concerns in oil and gas operations, particularly at high pressures and low temperatures such as those found in subsea or arctic environments. Practical adoption of icephobic/hydrate-phobic surfaces requires mechanical robustness and stability under harsh environments. Here, we develop durable and mechanically robust bilayer poly-divinylbenzene (pDVB)/poly-perfluorodecylacrylate (pPFDA) coatings using initiated chemical vapor deposition (iCVD) to reduce the adhesion strength of ice/hydrates to underlying substrates (silicon and steel). Utilizing a highly-cross-linked polymer (pDVB) underneath a very thin veneer of fluorine-rich polymer (pPFDA) we have designed inherently rough bilayer polymer films that can be deposited on rough steel substrates resulting in surfaces which exhibit a receding water contact angle (WCA) higher than 150° and WCA hysteresis as low as 4°. Optical profilometer measurements were performed on the films and root mean square (RMS) roughness values of Rq = 178.0 ± 17.5 nm and Rq = 312.7 ± 23.5 nm were obtained on silicon and steel substrates, respectively. When steel surfaces are coated with these smooth hard iCVD bilayer polymer films, the strength of ice adhesion is reduced from 1010 ± 95 kPa to 180 ± 85 kPa. The adhesion strength of the cyclopentane (CyC5) hydrate is also reduced from 220 ± 45 kPa on rough steel substrates to 34 ± 12 kPa on the polymer-coated steel substrates. The durability of these bilayer polymer coated icephobic and hydrate-phobic substrates is confirmed by sand erosion tests and examination of multiple ice/hydrate adhesion/de-adhesion cycles.