We demonstrate random lasing with star-shaped gold nanoparticles ("nanostars") as scattering centers embedded in a dye-doped gain medium. It is experimentally shown that star-shaped gold nanoparticles outperform those of conventional shapes, such as spherical or prolate nanoparticles. The nanoparticles are randomly distributed within a thin film of gain medium, forming resonators which support coherent laser modes. Driven by single-pulsed excitation, the random lasers exhibit coherent lasing thresholds in the order of 0.9 mJ/cm(2) and spectrally narrow emission peaks with linewidths less than 0.2 nm. The distinguished random laser comprising nanostars is likely to take advantage of the high plasmonic field enhancements, localized at the spiky tips of the nanostars, which improves the feedback mechanism for lasing and increases the emission intensity of the random laser.