Surface-enhanced Raman spectroscopy (SERS) is an emerging analytical technique for chemical analysis, which is favourable due to its combination of short measurement time, high sensitivity and molecular specificity. However, the application of SERS is still limited, largely because in real samples the analyte is often present in a complex matrix that contains micro/macro particles that block the probe laser, as well as molecular contaminants that compete for the enhancing surface. Here, we show a simple and scalable spray-deposition technique to fabricate SERS-active paper substrates which combine sample filtration and enhancement in a single material. Unlike previous spray-deposition methods, in which simple colloidal nanoparticles were sprayed onto solid surfaces, here the colloidal nanoparticles are mixed with hydroxyethyl cellulose (HEC) polymer before application. This leads to significantly improved uniformity in the distribution of enhancing particles as the film dries on the substrate surface. Importantly, the polymer matrix also protects the enhancing particles from air-oxidation during storage but releases them to provide SERS enhancement when the film is rehydrated. These SERS-paper substrates are highly active and a model analyte, crystal violet, was detected down to 4 ng in 10 μL of sample with less than 20% point-by-point signal deviation. The filter paper and HEC effectively filter out both interfering micro/macro particles and molecular (protein) contaminants, allowing the SERS-paper substrates to be used for SERS detection of thiram in mud and melamine in the presence of protein down to nanogram levels without sample pre-treatment or purification.