In many regions around the world, atmospheric icing during freezing rains and ice storms can cause severe damage to exposed infrastructure. Subsequently, protective coatings capable of ice accumulation prevention or ice adhesion reduction, often referred to as icephobic coatings, have gained a significant amount of interest. In this study, we examine an atmospheric-pressure plasma jet technique for the development of organosilicon-based icephobic coatings on aluminum substrates. Initially, Al-6061 samples are exposed to multiple passes of air plasma treatment at very short jet-to-substrate distances to create a microporous alumina-based surface structure. These surfaces are then used for plasma deposition of superhydrophobic coatings in the same jet with hexamethyldisiloxane (HMDSO) as the precursor and nitrogen as the plasma gas. Several samples are created with varying plasma precursor flow rates and number of deposition passes. All samples are exposed to three cycles of icing/de-icing to estimate coatings’ stability in aggressive natural conditions. The effects of multiple icing/de-icing cycles on surface chemistry, surface morphology, and wetting behavior is studied. It is shown that the most remarkable mechanism through which icing affects surface properties is coating removal during aggressive de-icing procedure. Finally, the icephobic properties of the most efficient coating (referred to as PT5x3) is further studied through 10 cycles of icing/de-icing, and it is shown that this coating can reduce ice adhesion strength by a factor of at least two for up to nine cycles of icing/de-icing.