Developing anti-icing coatings is an important topic for many scientists. In this work, we describe composite coatings prepared by a combination of plasma electrolytic oxidation and deposition of polytetrafluoroethylene from suspension. The composite layers obtained had high strength and adhesion to metal, which made it possible to use them in extreme environmental conditions. The change in the adhesion strength of ice to the coating surface was considered with various methods for forming composite layers on the surface of the metal and compared with the base PEO layer. The wettability of the resulting coatings as well as the relationship between the contact angle and the ice adhesion strength were evaluated.