A waveguide-plasmonic scheme is constructed by coating the matrix of randomly distributed gold nanoisland structures with a layer of dye-doped polymer, which provides strong feedback or gain channels for the emission from the dye molecules and enables successful running of a random laser. Excellent overlap of the plasmonic resonance of the gold nanoislands with the photoluminescence spectrum of the dye molecules and the strong confinement mechanism provided by the active waveguide layer are the key essentials for the narrow-band and low-threshold operation of this random laser. This kind of feedback configuration potentially enables directional output from such random lasers. The flexible solution-processable fabrication of the plasmonic gold nanostructures not only enables easy realization of such a random laser but also provides mechanisms for the tuning and multicolor operation of the laser emission.