Carbon materials are promising supports for heterogeneous catalysis compared to oxide supports, such as titania, alumina, mesoporous silica, and hydrotalcite, because of their stability and relative chemical inertness. Additionally, the unique surface structures of carbon supports help control the growth, aggregation, and uniformity of the catalytic nanoparticles (NPs) hybridized with them. However, the effect of carbon supports on these NP catalysts is not well understood, affecting the optimization of this type of catalysts. In this study, palladium-gold (Pd/Au) carbon composites were systematically investigated, and the most favorable carbon support was identified. Carbon-supported Pd/Au NPs have often been favored for catalytic hydrodehalogenation (HDH) of volatile organic compounds. Hence, this study uses trichloroethylene (TCE) as model contaminant to investigate the effects of four types of carbon supports—granular activated carbon (GAC), carbon black, graphite, and graphite nanoplates—on the formation of catalytic Pd/Au NPs and their correlations to HDH reactions. Each support was chosen based on a desirable quality: GAC has a large surface area and substantial absorption capabilities, carbon black has a high surface-area-to-volume ratio and good chemical stability, graphite is the most stable form of carbon with a layered structure and thermal stability, and graphite nanoplates have large surface areas with structural stability. Characterizations of these Pd/Au-carbon composites show different NP sizes on each support, with GAC and carbon black generating smaller NPs. The HDH results suggest GAC, carbon black, and graphite nanoplates composites generate fast reaction rates. However, when comparing particle size and surface area, Pd/Au-GAC composites generate the fastest TCE degradation, providing a bigger boost to HDH rates than other types of carbon supports. More advantageously, GAC is widely available commercially with relatively low cost, and its high surface area is enabled by its high porosity, making GAC the preferred carbon support for Pd/Au NP catalyst mass production.