In the present work, the role and the effect of platinum and gold on the catalytic performance of ceria supported tri-metallic Pt-Pd-Au catalysts have been studied. The optimum composition of these tri-metallic supported catalysts has been discovered using methods and tools of combinatorial catalyst library design. Detailed catalytic, spectroscopic and physico-chemical characterization of catalysts in the vicinity of the optimum in the given compositional space has been performed. The temperature-programmed oxidation of methane revealed that the addition of Pt and Au to Pd/CeO2 catalyst resulted in higher conversion values in the whole investigated temperature range compared to the monometallic Pd catalyst. The time-on-stream experiments provided further evidence for the high-stability of tri-metallic catalysts compared to the monometallic one. Kinetic studies revealed the stronger adsorption of methane on Pt-Pd/CeO2 catalysts than over Pd/CeO2. XPS analysis showed that Pt and Au stabilize Pd in a more reduced form even under condition of methane oxidation. FTIR spectroscopy of adsorbed CO and hydrogen TPD measurements provided indirect evidences for alloying of Pt and Au with Pd. CO chemisorption data indicated that tri-metallic catalysts have increased accessible metallic surface area. It is suggested that advantageous catalytic properties of tri-metallic Pt-Au-Pd/CeO2 catalysts compared to the monometallic one can be attributed to (i) suppression of the formation of ionic forms of Pd(II), (ii) reaching an optimum ratio between Pd0 and PdO species, and (iii) stabilization of Pd in high dispersion. The results also indicate that Pd0 - PdO ensemble sites are required for methane activation.