In this study, an electrochemical aptamer based sensor (aptasensor) was proposed for specific recognition of histamine (HIS). The electrochemical aptasensor based on fabrication of glassy carbon electrode (GCE) with molecular imprinted polymer (MIP) and DNA aptamers on gold nanoparticles (AuNPs) and carboxylated carbon nanotubes (cCNTs) (MIP-apta/AuNPs/cCNTs/GCE). The aptasensor exhibits high selectivity towards HIS detection as it has two recognition elements which are MIP cavities and aptamer interaction. Upon exposure of MIP-apt/AuNPs/cCNTs/GCE to HIS, the current of redox probe was decreased that depends on the template (HIS) concentration. The effects of aptamer concentration, incubation time, pH and AuNPs electro-deposition time were optimized. Differential pulse voltammetry (DPV) and electrochemical impedance spectroscopy (EIS) techniques were used to analyze HIS in complicated matrices. Favorable performance of MIP-apt/AuNPs/cCNTs/GCE was achieved with linearity ranges of 0.46–35 nmol L−1 and 0.35–35 nmol L−1 with limits of detection (LODs, S/N = 3) of 0.15 nmol L−1 and 0.11 nmol L−1 using DPV and EIS, respectively. The fabricated aptasensor displayed high selectivity, desirable reproducibility and stability. The MIP-apt/AuNPs/cCNTs/GCE was used to detect HIS in human plasma and canned tuna samples with good recoveries % and RSDs %.