The growth of nanostructured nickel : carbon (Ni : C) nanocomposite thin films by the supersonic cluster beam deposition of nickel and carbon clusters co-deposited from two separate beam sources has been demonstrated. Ni : C films retain the typical highly disordered structure with predominant sp(2) hybridization, low density, high surface roughness and granular nanoscale morphology of cluster assembled nanostructured carbon, but display enhanced electric conductivity. The electric double layer (EDL) capacitance of Ni : C films featuring the same thickness (200 nm) and different nickel volumetric concentrations (0-35%) has been investigated by electrochemical impedance spectroscopy employing an aqueous solution of potassium hydroxide (KOH 1 M) as electrolyte solution. Evidence of increased electric conductivity, facilitated EDL formation and negligible porous structure modification was found as consequence of Ni embedding. This results in the ability to synthesize electrodes with tailored specific power and energy density by the accurate control of the amount of deposited Ni and C clusters. Moreover, nickel nanoparticles were shown to catalyze the formation of tubular onion-like carbon structures upon mild thermal treatment in inert atmosphere. Electrochemical characterization of the heated nanocomposite electrodes revealed that the presence of long range ordered sp(2) structures further improves the power density and energy storage properties.