The combination of different nanomaterials such as metallic nanoparticles and carbon nanostructures in a new hybrid material should give rise to interesting properties that combine the advantages of each of the nanocomponents. This review highlights the latest advances in the synthetic design of these hybrid materials where carbon nanostructures act as supports as well as stabilizing agents for very reactive metallic nanoparticles. The striking applications of Pd nanoparticles anchored on the surface of carbon nanostructures in C-C coupling chemistry are analyzed. Special emphasis is placed on the stability of these materials, which is linked to their recyclability. Numerous examples are given that involve the use of these catalysts in Heck, Suzuki and Sonogashira coupling reactions.