We have used STM imaging in situ to demonstrate two fundamental steps in catalytic processes on model catalysts at elevated temperature. We show that Pd nanoparticles on sub-stoichiometric TiO2(110) dissociatively adsorb O-2 at 673 K which "spills over" onto the support where further reaction takes place. The spillover oxygen re-oxidises the surface by removing Tin+ interstitial ions trapped in the crystal lattice, preferentially re-growing TiO2 around and over the particles. The identification of the metal enhanced re-oxidation mechanism may have important and general consequences for the understanding of catalysis and gas sensing.