The adsorption of O atoms on the Fe(110) surface has been investigated by density functional theory for increasing degrees of oxygen coverage from 0.25 to 1 monolayer, to follow the evolution of the O-Fe(110) system into an FeO(111)-like monolayer. We found that the quasi-threefold site is the most stable adsorption site for all coverages, with adsorption energies of ~2.8 to 4.0 eV per O atom. Oxygen adsorption results in surface geometrical changes such as interlayer relaxation and buckling, the latter of which decreases with coverage. The calculated vibrational frequencies range from 265-470 cm-1 for the frustrated translational modes and 480-620 cm-1 for the stretching mode, and hence are in good agreement with the experimental values reported for bulk FeO wüstite. The hybridization of the oxygen 2p and iron 3d orbitals increases with oxygen coverage, and the partial density of states for the O-Fe(110) system at full coverage resembles the one reported in the literature for bulk FeO. These results at full oxygen coverage point to the incipient formation of an FeO(111)-like monolayer that would eventually lead to the bulk FeO oxide layer.