We demonstrated a facile fabrication of high density Au nanostructures including nanothorns (NTs), nanocorals (NCs), nanoslices (NSs), and nanowires (NWs) which were electrochemically grown on flexible plastic substrates of polyethylene terephthalate (PET). A thrombin-binding aptamer was immobilized on the surfaces of the Au nanostructures to form highly sensitive electrochemical impedance spectroscopic (EIS) biosensors for thrombin recognition. The binding of thrombin to the aptamer sequence was monitored by EIS in the presence of [Fe(CN)6]3-/4-(aq). The protein (1-50 pM) was detected linearly by the Au nanostructures. Among them, the Au NWs exhibited excellent thrombin detection performances. The biosensor provided high sensitivity, selectivity, and stability due to its high surface area.