The mechanism of CO oxidation by a CeO2(110)-supported gold atom has been investigated by DFT calculations. A novel stable surface structure has been identified in which one surface O atom of ceria migrates toward the isolated Au atom, resulting in a surface Au–O species that can react with CO. After CO2 desorption, the oxidation state of Au changes from positive to negative. In contrast to earlier explored CO oxidation mechanisms for single Au atoms on the CeO2(111) surface, O2 can adsorb in the vacancy created in the CeO2(110) surface adjacent to Au. In essence, the difference in O2 adsorption originates from the geometries of the two ceria terminations, pointing to strong structure sensitivity in the CO oxidation reaction. Dissociation of adsorbed O2 heals the O vacancy and leaves an additional O atom on the surface. At this stage the Au atom is positively charged so that CO can adsorb followed by facile formation of CO2 with the bridging O atom, closing the catalytic cycle. This mechanism successfully explains the role of surface O of ceria in CO oxidation by highly dispersed Au catalysts.