The safety of imported seafood products because of the contamination of prohibited substances, including crystal violet (CV) and malachite green (MG), raised a great deal of concern in the United States. In this study, a fractal-like gold nanostructure was developed through a self-assembly process and the feasibility of using surface-enhanced Raman spectroscopy (SERS) coupled with this nanostructure for detection of CV, MG, and their mixture (1:1) was explored. SERS was capable of characterizing and differentiating CV, MG, and their mixture on fractal-like gold nanostructures quickly and accurately. The enhancement factor of the gold nanostructures could reach an impressive level of approximately 4 x 10(7), and the lowest detectable concentration for the dye molecules was at approximately 0.2 ppb level. These results indicate that SERS coupled with fractal-like gold nanostructures holds a great potential as a rapid and ultra-sensitive method for detecting trace amounts of prohibited substances in contaminated food samples.