We describe the fabrication of highly conductive and large-area three dimensional pillared graphene nanostructure (PGN) films from assembly of vertically aligned CNT pillars on flexible copper foils for applications in electric double layer capacitors (EDLC). The PGN films synthesized via a one-step chemical vapor deposition process on flexible copper foils exhibit high conductivity with sheet resistance as low as 1.6 ohms per square and possessing high mechanical flexibility. Raman spectroscopy indicates the presence of multi walled carbon nanotubes (MWCNT) and their morphology can be controlled by the growth conditions. It was discovered that nitric acid treatment can significantly increase the specific capacitance of the devices. EDLC devices based on PGN electrodes (surface area of 565 m2/g) demonstrate enhanced performance with specific capacitance value as high as 330 F/g extracted from the current density-voltage (CV) measurements and energy density value of 45.8 Wh/kg. The hybrid graphene-CNT nanostructures are attractive for applications including supercapacitors, fuel cells and batteries.