In this study, phenolic novolac-type epoxy (EPN) resin was modified with 4 wt% thermoplastic polystyrene (PS) waste and was used as the polymer matrix for the first time. Two types of composites were prepared: (i) nanocomposites with 1–3 wt% nanoclay (NC) and (ii) hybrid composites. Pristine (NC) and tetramethylammonium chloride modified nanoclays (MNC) were used at a 2 wt% ratio in hybrid composites with 25–35 wt% red mud waste (RMW). The corrosion protection properties of the coatings were determined by immersion test in 5 wt% NaOH, HCl, and NaCl solutions. The water sorption of hybrid composites varied between 1%–3.6% and 1%–5.3%, while it was between 0.82% and 1.02% in EPN-PS/NC nanocomposites. The weight gain percentage values of hybrid composites in corrosive media for the base and salt solutions were determined much lower (0.59%–0.75% and 0.46%–0.59%, respectively) than water sorption. Surface morphologies of hybrid composites were examined by scanning electron microscopy before and after corrosion tests. MNC-30 wt% RMW hybrid composite was found more suitable due to high corrosion resistance in basic and salty environments, storage modulus, loss modulus, and glass transition temperature (Tg) values (90.6°C) as compared with NC-30 wt% RMW hybrid composite.