Model catalysts containing size-selected Pd n (n=1,2,4,7,10,16,20,25) deposited on rutile TiO 2 (110) deactivate during repeated CO oxidation temperature-programmed reaction (TPR) cycles, and the deactivation process has been probed using a combination of X-ray photoelectron spectroscopy (XPS), ultraviolet photoelectron spectroscopy (UPS), low-energy ion scattering (ISS), temperature-dependent ion scattering (TD-ISS), annealing experiments, and temperature-programmed desorption following exposure to CO and O 2 reactants. Results from such experiments suggest the cluster deactivation proceeds via an alloy-like, strong metal-support interaction (SMSI) effect that chemically modifies the clusters via electronic interactions between the supported metal atoms and Ti from the support. Threshold measurements show that this effect detrimentally affects CO-oxidation activity prior to the formation of an encapsulating overlayer by severely weakening the COPd bond strengths for binding configurations on top of the clusters. Oxidation appears to provide means of partially restoring the clusters to their initial state, but after sufficient exposure to reducing environments and elevated temperatures, all Pd n become covered by an overlayer and begin to electronically and chemically resemble freshly deposited atoms, which are completely inactive towards the probe reaction. In addition, we find evidence of oxygen spillover induced by co-adsorbed CO during TPRs for all active Pd n clusters.