In this work, a flexible and freestanding Carbon Nanofiber/Cobalt hydroxide (CNF/Co(OH)₂) composite paper is prepared via electrospinning followed by a simple chemical precipitation method. The structure characterizations show that Co(OH)₂ particles are well dispersed on the surface of the CNF, forming a thin and flexible composite paper. Due to the reinforcing effects coming from the double layer capacitance of CNF and the pseudo-capacitance of Co(OH)₂, the supercapacitive performance of pure CNF and pure Co(OH)₂ are mutually improved significantly after combination. The CNF/Co(OH)₂ paper exhibits the largest specific capacitance in the potential range of −1–0 V, about 24% higher than that of pure CNF paper; while the specific capacitance of the Co(OH)₂ can increase by 30% in the potential range of −0.2−0.35 V after precipitated on the CNF. Our work probably gives a new insight for designing and synthesizing electrode materials of supercapacitor and other energy-storage devices.