A novel gold coated tungsten nanofuzz array (TNFA) substrate has been prepared by irradiating polycrystalline tungsten using radio frequency plasma, followed by gold sputter coating. The surface morphology of the tungsten can be modified by tuning the irradiation parameters. The surface-enhanced Raman scattering (SERS) effect of the as prepared substrates has been tested using different molecule probes, namely, Rhodamine B (RHB), brilliant blue (X-BR) and reactive brilliant red (X-3B). Results show that the TNFA substrate exhibit the highest dye detection sensitivity (as low as <10 ppb) and excellent repeatability. A simple room temperature atmospheric pressure plasma treatment can be used to clean the substrate for re-use purpose through complete oxidization/degradation of the dye species. Systematic study reveals that the SERS enhancement effect is strongly dependent on the substrate surface morphologies and the laser excitation wavelength used. In addition, the SERS activity achieved by our novel substrate can be applied to a variety of dye molecules, demonstrating its potential to be generalized for a wider range of applications.