Two different carbon nanoforms (CNFs), namely multi-walled carbon nanotubes (MWCNTs) and carbon nanohorns (CNHs), have been chosen as support for the direct polymerization of a bis-vinylimidazolium salt. Transmission electron microscopy analyses revealed a templating effect of the CNFs on the growth of the polymeric network, which perfectly covers their whole surfaces creating a cylindrical or spherical coating for MWCNTs and CNHs, respectively. Subsequently, the CNFs-polyimidazolium have been used as stabilizers for Pd nanoparticles (Pd NPs), and the obtained materials have been characterized by means of analytical and spectroscopic techniques and then employed as easily recoverable and recyclable catalysts for Suzuki and Heck reactions. Quantitative conversions have been obtained in almost all the explored reactions, even employing low loading of catalyst (down to 0.007 mol%). Suzuki reactions were carried out in pure water under aerobic conditions. Both materials showed excellent activity and recyclability for the investigated C-C coupling reactions, with the CNHs-based material resulting slightly more active than the MWCNTs-based one due to a higher superficial exposure of Pd NPs.