This work describes the study of the electrochemical properties of fullerene polymer composites, C60-Pd, and different carbon nanostructures, such as single walled carbon nanotubes, multi walled carbon nanotubes and carbon nanoonions, as potential electrode materials for supercapacitors. The carbon nanostructures were deposited onto a bare gold disc electrode by a vapor deposition process. In the next step, the fullerene was electrochemically polymerized under cyclic voltammetric conditions. The obtained composites are electrochemically active at negative potentials due to the reduction of the fullerene moieties. The voltammetric response corresponding to this electrochemical process depends on the type of nanostructure and the amount of material deposited at the electrode surface. Such systems exhibit promising electrochemical properties. The highest capacitance of about 1000Fg−1, with respect to mass of polymer, was obtained for the SWCNTs/C60-Pd composite. This value is about four times higher compared to the capacitance of the polymer deposited on a bare gold electrode surface. Lower values of the specific capacitance were obtained for composites containing other MWCNTs and ox-CNOs. For the C60-Pd/ox-CNOs composites the highest values of the specific capacitance were found to be about 280Fg−1.