Pseudocapacitance is commonly associated to the reversible redox reactions from electrode materials, but the enhancement in pseudocapacitance that only relies on electrode materials is limited. Here, we explore the possibility of enhancing pseudocapacitance through both Co(OH)2/graphene nanosheets (GNS) electrode and K3Fe(CN)6 electrolyte. With a good conductivity and favoring electron transfer, GNS are hybridized with Co(OH)2 to improve the pseudocapacitance of Co(OH)2, including enhancing its rate capability and electrochemical stability. Adding K3Fe(CN)6 into KOH electrolyte further enhances the pseudocapacitance via both directly contributing pseudocapacitance to Co(OH)2/GNS and promoting the electron gain and loss of Co ions. This novel Co(OH)2/GNS-K3Fe(CN)6/KOH electrode system shows an ultrahigh specific capacitance of 7514 Fg−1 at 16 Ag−1 in mixed 1 M KOH and 0.08 M K3Fe(CN)6, more than 100% coulombic efficiency, and long-term cycling stability (the capacitance retention is 75% after 20000 continuous charge-discharge cycles in mixed 1 M KOH and 0.04 M K3Fe(CN)6).