Magnetization-induced optical surface second harmonic generation (SHG) in the longitudinal geometry was used to study magnetism on the p(1x1)O/Fe(001) surface during a layer-by-layer Fe growth with surfactant oxygen. Considerable one-monolayer oscillations were observed. Minima of the magnetization-induced contributions to the second order dielectric susceptibility were detected at half-filled monolayers. These contributions were accessed either by measuring a purely magnetic SHG yield, or indirectly from the magnetization dependence of the overall SHG signal, both providing consistent results. The origin of the oscillatory surface magnetism is consistent with the expected oscillating oxygen induced relaxation due to the surface Fe islands.