The different morphologies of Co films grown on either the clean Fe(001) surface and the oxygen-saturated Fe(001)-$p(1\times 1)\mathrm{O}$ substrate are investigated by means of scanning tunneling microscopy, Auger electron spectroscopy, and density functional theory. The considered Co coverage range extends beyond the thickness at which layer-by-layer growth is destabilized by plastic deformations induced by the relaxation of the strain accumulated in the film. Our findings indicate that the oxygen overlayer of the Fe(001)-$p(1\times 1)\mathrm{O}$ surface floats on top of the growing Co film and strongly influences both the Co nucleation process and the film structural evolution. The layer-dependent islands nucleation of Co films grown on clean Fe(001) substrates, recently associated with a thickness-dependent adatom mobility [A. Picone et al., Phys. Rev. Lett. 113, 046102 (2014)], is found to be suppressed by the oxygen overlayer. The latter also significantly delays the layer-by-layer instability with respect to the oxygen-free growth. Furthermore, the body-centered-tetragonal/hexagonal-close-packed transition is not observed in the case of Co/Fe(001)-$p(1\times 1)\mathrm{O}$ sample, replaced by the development of highly ordered surface undulations. These form a mesoscopic square pattern with the sides aligned to the $\mathrm{Fe}\langle 110\rangle$ directions, while the surface atomic structure retains the square $p(1\times 1)$ symmetry in registry with the substrate. Such undulations are likely generated by a highly ordered array of interfacial misfit dislocations running along the $\mathrm{Fe}\langle 110\rangle$ directions.