Palladium oxide surface structures with different oxygen stoichiometries, that were searched for by particle swarm optimization, are investigated for their methane combustion activity. Three distinct surface phases were identified: Chemisorbed oxygen, PdOX surface oxide, and bulklike PdO supported on a palladium surface. The PdOX surface oxides are found to be the most interesting, composed of metal Pd patches and PdO patches, with a distinct oxide interphase between these patches. Through DFT calculations, a PdOX surface is heat-mapped for methane C-H activation barriers. Pd metal patches are found to be the most active sites and PdO patches the least active. A total combustion of methane pathway is calculated on the Pd patch, the PdO patch, and the interphase between these patches on the generated PdOX surface. These results are compared to the pathway on a Pd(111) surface. Dehydrogenation steps are found to be favored on Pd patches, while oxidation steps are favored on PdO patches. It is demonstrated that the most active palladium surface for methane combustion contains both metal and oxide phases.