Corrosion prevention and infrared (IR) stealth are conflicting goals. While graphene nanosheets (GN) provide an excellent physical barrier against corrosive agent diffusion, thus lowering the permeability of anti-corrosion coatings, they have the side-effect of decreasing IR stealth. In this work, the anti-corrosion properties of 100-μm-thick composite epoxy coatings with various concentrations (0.01–1 wt.%) of GN fillers thermally reduced at different temperatures (300 °C, 700 °C, 1100 °C) are first compared. The performance was characterized by potentiodynamic polarization scanning, electrochemical impedance spectroscopy, water contact angle and salt spray tests. The corrosion resistance for coatings was found to be optimum at a very low filler concentration (0.05 wt.%). The corrosion current density was 4.57 × 10−11 A/cm2 for GN reduced at 1100 °C, showing no degradation after 500 h of salt-spray testing: a significant improvement over the anti-corrosion behavior of epoxy coatings. Further, to suppress the high IR thermal signature of GN and epoxy, Al was added to the optimized composite at different concentrations. The increased IR emissivity due to GN was not only eliminated but was in fact reduced relative to the pure epoxy. These optimized coatings of Al-GN-epoxy not only exhibited greatly reduced IR emissivity but also showed no sign of corrosion after 500 h of salt spray test.