Gold nanocrystal-modified glassy carbon electrodes (nAu-GCE) were prepared and used for the determination of histamine by flow injection and high performance liquid chromatography using pulsed amperometric detection (PAD) as the detection mode. Experimental variables involved in the electrodeposition process of gold from a HAuCl4 solution were optimized. A catalytic enhancement of the histamine voltammetric response was observed at the nAu-GCE when compared with that obtained at a conventional Au disk electrode, as a consequence of the microdispersion of gold nanocrystals on the GC substrate. The morphological and electrochemical characteristics of the nAu-GCE were evaluated by SEM and cyclic voltammetry. PAD using a very simple potential waveform consisting of an anodic potential (+700 mV for 500 ms) and a cathodic potential (−300 mV for 30 ms), was used to avoid the electrode surface fouling when histamine was detected under flowing conditions. Flow injection amperometric responses showed much higher Ip values and signal-to-noise ratios at the nAu-GCE than at a conventional gold disk electrode. A limit of detection of 6×10−7 mol L−1 histamine was obtained. HPLC-PAD at the nAu-GCE was used for the determination of histamine in the presence of other biogenic amines and indole. Histamine was determined in sardine samples spiked at a 50 μg g−1 concentration level, with good results. Furthermore, the chromatographic PAD method was also used for monitoring the formation of histamine during the decomposition process of sardine samples.