Preventing ice formation on surfaces (anti-icing) and easy removal of ice formed on surfaces (de-icing) are of great technological importance for aircraft and overhead power lines. This has been effected by the use of coatings. A wide variety of coatings have been reported that delay frost formation or that afford the removal of deposited ice. However, there is a need for coatings that simultaneously exhibit anti-icing and de-icing properties and that are robust to multiple freeze-thaw cycles. Here, we report a two-phase coating comprising a soft gel-phase swollen with freezing point depressant, encapsulated in a hydrophobic, rigid elastomeric matrix phase. Since the coating is comprised predominantly of the soft gel phase (70% by vol.) embedded in the rigid matrix (minority phase, 30% by vol), it exhibits a low elastic modulus while maintaining good mechanical durability. This coating exhibits exceptional performance, with an unprecedented combination of frost inhibition and removal of surface ice at very low stresses when compared with previously reported coatings. In particular, frosting takes over 200 minutes for a surface temperature of −20^°C at ambient conditions of 28^°C and 60% RH, compared to less than 20 minutes for superhydrophobic or liquid-infused slippery coatings. Further, these coatings are characterized by an adhesion stress ≈10 kPa, lower than even that for stress localized surfaces (≈ 40 − 50 kPa). Additionally, the anti-icing and de-icing performance of this coating is robust to multiple freeze-thaw cycles. In contrast to previously reported elastomeric coatings, de-icing is not due to stress localization - rather, it likely arises from local melting at the surface of the deposited ice by the action of the freezing point depressant. We attribute the exceptional performance of the coating to a combination of the overall low elastic modulus of the coating, with the slow release of hydrophilic freezing point depressant through the matrix.