We report an ultra-sensitive surface-enhanced Raman scattering (SERS)-based detection system for 2,4,6-trinitrotoluene (TNT) using nano-dumbbell structures formed by the electrostatic interaction between positively and negatively charged gold nanoparticles. First, Meisenheimer complexes were produced between TNT and l-cysteine on gold substrates, and 4-mercaptopyridine (4-MPY) labeled gold nanoparticles (positively charged) were allowed to interact with the Meisenheimer complexes through the electrostatic interaction between the negatively charged aromatic ring of the complex molecules and the positively charged nanoparticles. Then, negatively charged gold nanoparticles were added in order to form nano-dumbbells. As a result, many hot junctions were generated by the dumbbell structures, and the SERS signals were greatly enhanced. Our experimental results demonstrate that the SERS-based assay system using nano-dumbbells provides an ultra-sensitive approach for the detection of TNT explosives. It also shows strong potential for broad application in detecting various explosive materials used for military purposes.