We demonstrate in this work a unique strategy for the synthesis of heterogeneous Pd catalysts with the use of a hyperbranched poly(phenylacetylene) containing pendant alkyne groups as the cross-linkable polymer substrate. It utilizes the dual functions of Pd-based catalysts in catalyzing both alkyne polymerization/oligomerization and coupling reactions. In the synthesis, a homogeneous Pd(II) catalyst catalyzes the cross-linking of the hyperbranched polymer and simultaneously encapsulates itself into the cross-linked polymer matrix, rendering the heterogeneous catalyst at high yield and high percentage of Pd encapsulation. Three homogeneous catalysts having different ligands (triphenylphosphine, a diphosphine ligand, and a diimine ligand) have been examined for the cross-linking encapsulation and the resulting heterogeneous catalysts have been evaluated for their catalytic performance in coupling reactions. Among the various heterogeneous catalysts obtained, a triphenylphosphine-ligated catalyst, HBPPA-Pd-2, appears to be the optimum one. It shows high activity in catalyzing the Suzuki–Miyaura reactions, the Mizoroki–Heck reactions, and the allylic arylation reactions under air with the Pd loading at as low as mol ppm or even mol ppb levels relative to the reactants. Meanwhile, it facilitates the Suzuki–Miyaura reactions of challenging less reactive aryl chlorides/heteroaryl bromides and the Mizoroki–Heck reactions of aryl bromides as reactants. In addition, it behaves truly as a heterogeneous catalyst with high reusability and low catalyst leaching during the reactions.