Understanding the catalytic properties of metal/metal oxide interfaces is gaining importance in heterogeneous catalysis. Density functional theory calculations were employed to understand the mechanism of CO oxidation on TM/SrTiO3 catalysts (TM/STO, TM = Au, Ag, Pd, Pt, Rh, and Ir). Au benefits from O2 dissociation at the Au/STO interface with lower barrier than on corresponding closed-packed Au surface. Doping of STO with fluorine lowers the activation barriers for O2 dissociation. Brønsted-Evans-Polanyi relations are identified for O2 dissociation and a density of states analysis provides insight into the activation of O2 at TM/STO interfaces. Full catalytic cycles for CO oxidation are formulated including O2 dissociative and associative mechanisms. Microkinetics simulations show that an O2 associative mechanism at Au/STO and Ag/STO interfaces is dominant for CO oxidation. For a more reactive metal like Pd, CO2 formation involving interface sites present higher barriers than on the metal itself because of too strong binding of O at the Pd/STO interface. Pt/STO and Rh/STO also follow such a conventional Langmuir-Hinshelwood mechanism, while Ir is too reactive leading to a shift of the reaction at the Ir/STO interface involving dissociated O2. The mechanistic insights are discussed with respect to recent experimental literature on Pd/STO and Au/STO for which different structure-performance relationships were formulated. We predict that F-doping of STO can further improve the catalytic performance of TM/STO catalysts for CO oxidation.