We report a novel approach for fabricating gold nanostar-functionalized substrates for highly sensitive surface enhanced Raman spectroscopy (SERS)-based chemical sensing. Gold nanostars immobilized on a gold substrate via a Raman silent organic tether serve as the SERS substrate, and facilitate the chemical sensing of analytes that can either be chemisorbed or physisorbed on the nanostars. Our SERS substrates are capable of detecting chemisorbed 4-mercaptobenzoic acid at a concentration as low as 10 fM with a reproducible SERS enhancement factor of 10(9), and enable the semi-quantitative multiplexed identification of analytes from mixtures in which they have been dissolved in variable stoichiometry. Most importantly, they afford the detection of physisorbed analytes, such as crystal violet, with an excellent signal-to-noise ratio, hence serving as a versatile platform for the chemical identification of in principle any molecular analyte. These characteristics make a strong case for the use of our nanostar-based SERS substrate in practical chemical sensing applications.