Methane adsorption and dehydrogenation on nanometer-sized Pt clusters, supported by reduced ceria (110), was investigated using density functional theory with Hubbard corrections. Two Pt nanocluster shapes, hemispherical and tetrahedral, are considered. Both stoichiometric and reduced ceria do facilitate methane adsorption and dehydrogenation on the supported clusters, as compared to unsupported clusters; an analogous beta-silica support does not significantly enhance methane adsorption. The energy barrier to activation decreases by approximately 0.06 eV for hemispherical Pt/CeO2-x and 0.12 eV for tetrahedral Pt/CeO2-x, compared to the unsupported clusters. Methane adsorbs preferentially atop the Pt atoms at the metal-support interface; upon dehydrogenation, H migrates to the oxygen vacancy site on the ceria surface while CH3 remains on the Pt cluster. We propose that the increased electron density and compressive strain at the low-coordinated Pt sites and oxygen vacancies at the metal-support interface contribute cooperatively to the enhanced catalytic activity. Our results confirm the critical role of support structure and composition for catalytic methane activation and dehydrogenation on noble metal clusters.