Conspectus Methane complete oxidation is an important reaction that is part of the general scheme used for removing pollutants contained in emissions from internal combustion engines and, more generally, combustion processes. It has also recently attracted interest as an option for the removal of atmospheric methane in the context of negative emission technologies. Methane, a powerful greenhouse gas, can be converted to carbon dioxide and water via its complete oxidation. Despite burning methane being facile because the combustion sustains its complete oxidation after ignition, methane strong C-H bonds require a catalyst to perform the oxidation at low temperatures and in the absence of a flame so as to avoid the formation of nitrogen oxides, such as those produced in flares. This process allows methane removal to be obtained under conditions that usually lead to higher emissions, such as under cold start conditions in the case of internal combustion engines. Among several options that include homo- and heterogeneous catalysts, supported palladium-based catalysts are the most active heterogeneous systems for this reaction. Finely divided palladium can activate C-H bonds at temperatures as low as 150 °C, although complete conversion is usually not reached until 400-500 °C in practical applications. Major goals are to achieve catalytic methane oxidation at as low as possible temperature and to utilize this expensive metal more efficiently. Compared to any other transition metal, palladium and its oxides are orders of magnitude more reactive for methane oxidation in the absence of water. During the last few decades, much research has been devoted to unveiling the origin of the high activity of supported palladium catalysts, their active phase, the effect of support, promoters, and defects, and the effect of reaction conditions with the goal of further improving their reactivity. There is an overall agreement in trends, yet there are noticeable differences in some details of the catalytic performance of palladium, including the active phase under reaction conditions and the reasons for catalyst deactivation and poisoning. In this Account we summarize our work in this space using well-defined catalysts, especially model palladium surfaces and those prepared using colloidal nanocrystals as precursors, and spectroscopic tools to unveil important details about the chemistry of supported palladium catalysts. We describe advanced techniques aimed at elucidating the role of several parameters in the performance of palladium catalysts for methane oxidation as well as in engineering catalysts through advancing fundamental understanding and synthesis methods. We report the state of research on active phases and sites, then move to the role of supports and promoters, and finally discuss stability in catalytic performance and the role of water in the palladium active phase. Overall, we want to emphasize the importance of a fundamental understanding in designing and realizing active and stable palladium-based catalysts for methane oxidation as an example for a variety of energy and environmental applications of nanomaterials in catalysis.