The accumulation of ice on man-made structures can limit the performance of those structures, and also can cause destructions in major industries, such as aviation, automotive, ship, trains, highways, telecommunication, defense, and many others. The National Aeronautics and Space Administration Aviation Safety Reporting System reported from the years 2006 to 2010, 228 icing-related accidents and 30 inflight-related incidents took place. The removal of formed ice includes spraying chemicals and heating using various techniques, which are costly, time-consuming, and sometimes risky. This work investigates the enhancing of deicing capabilities of carbon fiber-reinforced composite using superhydrophobic coatings. A double coating system was sprayed on pre-impregnated (pre-preg) fiber reinforced composites to form superhydrophobic surfaces, and then the coated composites were treated to improve its bonding. Experimental test results showed that superhydrophobic coatings play a significant role in deicing of fiber-reinforced composites. The accumulated ice, that is formed on superhydrophobic-coated composite materials can be removed easily either by placing the material at an angle, mechanical vibration, or air blowing. Promising contact angles above 150° were revealed that after performing a de-icing test multiple times, the samples provided excellent deicing capabilities. This may be a useful approach to deice the aircraft, other transportation units and highway systems.