Preexposure to molecular oxygen gas, O2,g , can have a strong effect on the nucleation and growth of Ag islands on Ag(100) at 250 K. At this temperature, molecular oxygen dissociates efficiently at kink sites on steps. Subsequent deposition of Ag produces a far lower density of Agad islands than without oxygen. There is an associated increase in the Ag flux-scaling exponent, from 0.28 for the oxygen-free surface to 0.9 for the preexposed surface. Two-step deposition experiments show that species containing atomic oxygen diffuse freely across terraces and steps at this temperature and on the time scale of deposition.We hypothesize that the nucleating species contains both Ag and O, and that nucleation of islands is highly reversible ~critical size i>>1). The diffusion of small islands, if it occurs, is not sufficient to explain the data.