In this work, a flexible and freestanding carbon nanofiber/graphene nanosheet (CNF/GNS) composite paper is prepared via electrospinning followed by high-temperature annealing using a polyacrylonitrile/GNS/dimethylformamide mixture as electrospun precursor. The structure characterizations show that GNS homogeneously distributes in the CNF, forming a thin, light-weight and flexible composite paper. Due to the reinforcing effects coming from CNF and GNS, the Brunauer Emmett Teller (BET) specific surface area, conductivity and capacitance performance of pure CNF are significantly improved after adding GNS. The GNS/CNF composite paper exhibits the largest specific capacitance of 197Fg−1, about 24% higher than that of pure CNF paper. Therefore, based on the above investigations, such GNS/CNF composite paper can be a potential candidate for high-performance flexible capacitors.