Interactions between a metal and its oxide support can influence CO and CH4 oxidation, but promotion by the support can be difficult to study because oxides can have different surface structures and surface areas. To focus on the chemical aspects of support promotion for CO and CH4 oxidation, this study investigated the effect of support composition on Pd catalysts by preparing uniform films of NiO, Co3O4, Fe2O3, MnO2, CeO2, and ZrO2 on -Al2O3 using Atomic Layer Deposition (ALD). The structure of the films was characterized by XRD and STEM, and catalysts with similar to 1-wt% Pd were examined for CO and CH4 oxidation. CeO2/-Al2O3 was unique among the supports in greatly stabilizing the Pd dispersion to 1173K. Rates for CO oxidation were enhanced by the presence of CeO2, Fe2O3, and MnO2, while the other oxides had no promotional effect. For CH4 oxidation, only NiO and Co3O4 were modest promoters, while the other reducible oxides even showed a negative effect on rates. Possible reasons for the differences between CH4 and CO oxidation activities are discussed.