The reactivities of the stoichiometric and partially reduced rutile TiO2(110) surfaces towards oxygen adsorption and carbon monoxide oxidation have been studied by means of periodic density functional theory calculations within the Car-Parrinello approach. O-2 adsorption as well as CO oxidation are found to take place only in the presence of surface oxygen vacancies (partially reduced surface). The oxidation of CO by molecularly adsorbed O-2 at the O-vacancy site is found to have an activation energy of about 0.4 eV. When the adsorbed O-2 is dissociated, the resulting adatoms can oxidize incoming gas-phase CO molecules with no barrier. In all studied cases, once CO is oxidized to form CO2, the resulting surface is defect-free and no catalytic cycle can be established. (C) 2004 American Institute of Physics.