We present here an efficient and simple method for preparation of highly active Pd heterogeneous catalyst (CNT-Pd), specifically by reaction of dichlorobis(triphenylphosphine)palladium ($Pd(PPh_3)_2Cl_2$) with thiolated carbon nanotubes (CNTs). The as-prepared CNT-Pd catalysts demonstrated an excellent catalytic activity for the carbon-carbon (C-C) cross-coupling reactions (i.e. Suzuki, Stille, and decarboxylative coupling reactions) under mild conditions. The CNT-Pd catalyst could easily be removed from the reaction mixture; additionally, in the decarboxylative coupling of iodobenzene and phenylpropiolic acid, it showed a six-times recyclability, with no loss of activity. Moreover, once its activity had decreased by repeated recycling, it could easily be reactivated by the addition of phosphine ligands. The remarkable recyclability of the decarboxylative coupling reaction is attributable to the high degree of dispersion of Pd catalysts in CNTs. Aggregation of the Pd catalysts is inhibited by their strong adhesion to the thiolated CNTs during the chemical reactions, thereby permitting their recycling.