The energetics of the catalytic oxidation of CO on a complex metal oxide are investigated for the first time via density functional theory calculations. The catalyst, Co-doped SrTiO3, is modelled using periodically repeated slabs based on the SrTiO3(100) surface. The comparison of the energy profiles obtained for the pure host and the Co-doped material reveals the actual pathway followed by the reaction, and shows that Co doping enhances the catalytic properties of SrTiO3 by reducing the energy cost for the formation of oxygen vacancies.