To overcome deactivation of Pd-based catalysts at high temperatures, we herein design a novel pathway by introducing a certain amount of CoO to the supported Au-Pd alloy nanoparticles (NPs) to generate high-performance Au-Pd-xCoO/three-dimensionally ordered macroporous (3DOM) Co3O4 (x is the Co/Pd molar ratio) catalysts. The doping of CoO induced the formation of PdO-CoO active sites, which was beneficial for the improvement in adsorption and activation of CH4 and catalytic performance. The Au-Pd-0.40CoO/3DOM Co3O4 sample performed the best (T90% = 341 °C at a space velocity of 20 000 mL g-1 h-1). Deactivation of the 3DOM Co3O4-supported Au-Pd, Pd-CoO, and Au-Pd-xCoO nanocatalysts resulting from water vapor addition was due to the formation and accumulation of hydroxyl on the catalyst surface, whereas deactivation of the Pd-CoO/3DOM Co3O4 catalyst at high temperatures (680-800 °C) might be due to decomposition of the PdOy active phase into aggregated Pd0 NPs. The Au-Pd-xCoO/3DOM Co3O4 nanocatalysts exhibited better thermal stability and water tolerance ability compared to the 3DOM Co3O4-supported Au-Pd and Pd-CoO nanocatalysts. We believe that the supported Au-Pd-xCoO nanomaterials are promising catalysts in practical applications for organic combustion.