A new graphene/nickel-iron-hexacyanoferrate (graphene/Ni-Fe-HCF) nanocomposite was constructed and its electrochemical behavior was investigated. First, graphene oxide (GO) was deposited by electrophoretic deposition (EPD) technique onto stainless steel (SS). Then, it was electrochemically reduced to graphene (ERGO/SS) by applying constant potential at −1.1 V in NaNO3. Finally, Ni-Fe-HCF hybrid was formed onto ERGO/SS from solution containing NiCl2, FeCl3 and K3Fe(CN)6 by chronoamperometry. The surface morphology of constructed electrode was studied using scanning electron microscopy (SEM) and atomic force microscopy (AFM). SEM indicates the formation of nanoparticles in the range of 20–60nm. Also, crystal structure of nanocomposite was characterized by using X-ray diffraction. The performance of prepared electrode was investigated by various electrochemical methods using cyclic voltammetry, galvanostatic charge-discharge and electrochemical impedance spectroscopy (EIS). Results show that Ni-Fe-HCF hybrid has characteristics of battery-type materials. Ni-Fe-HCF/ERGO nanocomposite has higher capacity (67.77mAhg−1) than ERGO (32.5mAhg−1) or Ni-Fe-HCF (20.97mAhg−1) at 0.5Ag−1. Also, its capacity is higher than that of Ni-HCF/ERGO (44.58mAhg−1) or Fe-HCF/ERGO (44.72mAhg−1) at same current density. In addition, EIS results show Ni-Fe-HCF/ERGO has the lowest charge transfer resistance. Cycle life studies resolve that Ni-Fe-HCF/ERGO shows good stability in 0.5M KNO3 at pH=5.