To limit further rising levels in methane emissions from stationary and mobile sources and to enable promising technologies based on methane, the development of efficient combustion catalysts that completely oxidize CH4 to CO2 and H2O at low temperatures in the presence of high steam concentrations is required. Palladium is widely considered as one of the most promising materials for this reaction, and a better understanding of the factors affecting its activity and stability is crucial to design even more improved catalysts that efficiently utilize this precious metal. Here we report a study of the effect of three important variables (particle size, support, and reaction conditions including water) on the activity of supported Pd catalysts. We use uniform palladium nanocrystals as catalyst precursors to prepare a library of well-defined catalysts to systematically describe structure–property relationships with help from theory and in situ X-ray absorption spectroscopy. With this approach, we confirm that PdO is the most active phase and that small differences in reaction rates as a function of size are likely due to variations in the surface crystal structure. We further demonstrate that the support exerts a limited influence on the PdO activity, with inert (SiO2), acidic (Al2O3), and redox-active (Ce0.8Zr0.2O2) supports providing similar rates, while basic (MgO) supports show remarkably lower activity. Finally, we show that the introduction of steam leads to a considerable decrease in rates that is due to coverage effects, rather than structural and/or phase changes. Altogether, the data suggest that to further increase the activity and stability of Pd-based catalysts for methane combustion, increasing the surface area of supported PdO phases while avoiding strong adsorption of water on the catalytic surfaces is required. This study clarifies contrasting reports in the literature about the active phase and stability of Pd-based materials for methane combustion.