In this paper, we demonstrated for the first time the growth of 3D networks of graphene nano-flakes across porous stainless steel substrates of micron sized metal fibres, and its anti-corrosion properties. The controlled formation of graphene-grade coatings in the form of single sheets to complex and homogeneously distributed 2-4 µm long nano-pillars is demonstrated by Scanning Electron Microscopy. The morphology and stability of these structures are shown to be particularly related to the temperature and feed gas flow rate during the growth. The number of layers across the graphene materials was calculated from the Raman spectra and is shown to range between 3 and more than 15 depending on the growth conditions and to be particularly related to the time and flow rate of the experiment. The presence of the graphene was shown to massively enhance the specific surface area of the material and to contribute to the increased corrosion resistance and electrical conductivity of the material without compromising the properties or structure of the native stainless steel materials. This new approach opens up a new route to the facile fabrication of advanced surface coatings with potential applications in developing new thermal exchangers, separation and bio-compatible materials.