A novel surface-enhanced Raman spectroscopy (SERS) method has been developed for the sensitive and selective detection of nicotine in heated tobacco products (HTPs) and cigar using biosynthesized gold nanoparticles (GNPs) from Sargassum plagiophyllum seaweed extract. A polycrystalline structure was observed in the biosynthesized GNPs, which showed a uniform spherical shape. Optimization of SERS substrates revealed that a 20-fold concentrated GNP solution provided the highest SERS intensity and the lowest background signal intensity. The developed SERS method demonstrated a linear range (1 nM to 1 μM), low limit of detection (0.2 nM), and excellent reproducibility. The biosynthesized GNP-based substrates showed a significantly higher enhancement factor (2.5 × 106) and better reproducibility than commercial SERS substrates. The applicability of the method to nicotine analysis in real HTP samples was validated, with recoveries ranging from 92.5 to 108.3% and minimal matrix effects (MEP: −5.2 to 3.8%). The eco-friendly biosynthesis of GNPs, combined with the inexpensive and disposable paper-based substrates, makes this method a promising tool for the rapid and reliable quantification of nicotine in HTPs and cigar.