Adsorption and coadsorption of carbon monoxide and oxygen on different types of Au clusters on R(15 × 3)C/W(110) and R(15 × 12)C/W(110), respectively, are studied with respect to the catalytic behavior for oxidation of CO as well as of surface carbon. Carburization of the W(110) surface results in a weakening of the adsorption bond for molecularly adsorbed CO. Dissociation of carbon monoxide, which occurs on W(110), is reduced on the low-carbon coverage R(15 × 12) surface and completely suppressed on the carbon-saturated R(15 × 3) phase. Deposition of gold results in a blocking of adsorption sites for molecularly adsorbed CO and reopening of the dissociation channel. Probably the latter is associated with the existence of double-layer gold clusters and islands. At room temperature the gold clusters on both carburized templates are stable in CO atmosphere as shown by in-situ STM measurements. In contrast, exposure to oxygen alters the clusters on the R(15 × 12) surface, implying dissociation of oxygen not only on the substrate but also on or in immediate vicinity of the gold clusters. On the Au-free carburized templates oxygen adsorbs dissociatively and is released as CO at temperatures beyond 800 K due to reaction with carbon atoms from the templates. Deposition of gold enhances the desorption rate of the formed CO at the low-temperature end of the recombinative CO desorption range, indicating a promoting effect of gold for oxidation of surface carbon. In contrast, low-temperature CO oxidation catalyzed by the deposited Au clusters is not observed. Two reasons could be identified: (1) weakly bound CO with desorption temperatures between 100 and 200 K (as reported for other related systems) is not observed, and (2) oxygen atoms are bonded too strongly to the templates.