The accumulation of ice on structures can restrict the performance of equipment and cause other concerns in many industries such as aviation, automotive transportation, telecommunication, and defense. The removal of ice requires the use of some chemicals and various other techniques, which are expensive, time-consuming, and unsafe. Superhydrophobic (SH) coatings have been involved in many commercial applications because they have the crucial attribute of high water repellency, which can be critical for the removal of formed ice. This study experimentally proved how a carbon fiber-reinforced (CFR) composite surface can be prepared so that ice that forms on the surface can be easily removed without applying any other techniques. A simple spraying method was implemented to prepare a robust SH coating containing micro- and nanoparticles on unidirectional pre-impregnated (pre-preg) CFR composites that were prepared in a vacuum oven. The bottom (base) coat and top coat (superhydrophobic) were subsequently introduced to the surfaces of CFR composites, followed by heat treatment under a vacuum. The SH-coated CFR composites were analyzed through water contact angle (WCA) measurements. These measurements were also repeated after each tape adhesion test, vibration test, and blowing air test. The SH-coated CFR composites were exposed to a freezing time test and super-cooled water test, and then examined through an optical microscope. The SH-coated CFR composite had a maximum WCA of 163°. The coating tests on the SH-coated CFR composites showed that the WCA of the SH-coated CFR composite was steady and long-lasting after each test, which was considered as a permanent superhydrophobic surface. Thus, the de-icing and anti-icing properties of the SH-coated CFR composite were achieved, which is an important factor for a longer service time of composites used in aerospace, wind turbines, and other industries.