Pd nanoparticles (NPs) supported on polyaniline (PANI)-coated carbon nanotubes (CNTs) were synthesized using a low-cost and simple method for application in the Heck reaction. The effects of the PANI/CNT coating weight ratio on the catalytic stability and recyclability of the composite were determined by using a combination of experimental and computational methods. The results show that through coordination of the N-species in PANI with the Pd NPs, the nitrogen-rich PANI@CNT provides a strong support for the Pd NPs. The thickness of the PANI layer is the key in determining the stability of the catalyst. PANI becomes protonated in the presence of CNTs, as electron transfer from the former to the latter creates strong interactions between the two. Thus, PANI becomes more stable in nanocomposites with a higher CNT content, e.g., PANI/CNT = 0.5 : 1. The catalyst with a PANI/CNT ratio of 0.5 : 1 exhibited the best recycling performance, and only a small loss of activity was observed after 10 cycles. However, upon increasing the PANI content (e.g., PANI/CNT = 4 : 1), the PANI units tend to form bulk structures that are less stable than those that wrap around the CNTs. Such a structure is unstable; therefore, the PANI layers can easily deform or break away from the CNT backbones. Hence, these catalysts deactivate during recycling. Thus, our study demonstrates that the assembly of noble-metal NPs on CNTs bearing a thin coaxial PANI coating is a powerful technique to prepare reusable catalysts for the Heck reaction. Coating thickness is also a key factor affecting the efficiency and stability of the catalyst.