From an interplay between scanning tunneling microscopy, temperature programmed desorption, X-ray photoelectron spectroscopy, and density functional theory calculations we have studied low-temperature CO oxidation on Au/Ni(111) surface alloys and on Ni(111). We show that an oxide is formed on both the Ni(111) and the Au/Ni(111) surfaces when oxygen is dosed at 100 K, and that CO can be oxidized at 100 K on both of these surfaces in the presence of weakly bound oxygen. We suggest that low-temperature CO oxidation can be rationalized by CO oxidation on O(2)-saturated NiO(111) surfaces, and show that the main effect of Au in the Au/Ni(111) surface alloy is to block the formation of carbonate and thereby increase the low-temperature CO(2) production.