This work aims to develop and characterize a new design of free-standing interconnected carbon nanofiber electrodes for supercapacitor application. The fibers are obtained via carbonization of three components of electrospun nanofiber mats based on a polyacrylonitrile polymer (as a carbon backbone precursor), polyvinylalcohol (as a sacrificial copolymer), and 0-1.0 wt% multi-walled carbon nanotubes. Carbonizing these ternary composites results in fibers with about twice as large in surface area and one order of magnitude higher in electrical conductivity than those obtained by the carbonization of neat polyacrylonitrile and/or binary polyacrylonitrile-0-1.0 wt% carbon nanotube mats. The carbonized polyacrylonitrile-polyvinylalcohol-0.3 wt% carbon nanotube mat reveals the highest surface area and electrical conductivity and best capacitive performance. It exhibits energy and power densities of 27.8 Wh kg-1 and 110.59 kW kg-1, respectively, and cyclic stability of 95% after 2000 charge-discharge cycles at a charging current of 1.0 Ag-1. The nanotubes' alignment along the fiber's axis, the formation of fiber-fiber interconnected morphology with more mesopore pollution, and changes in the graphitization degree and defect features of fiber crystallites are the reasons for the observed increase in the electrical conductivity, surface area, and capacitive performance of the carbon fibers. Therefore, the new design represents a potential free-standing carbon nanofiber electrode for future electrochemical double layer capacitor (EDLC) device fabrication.