Density functional theory in combination with genetic algorithm is applied to determine the atomic models of p(1x2) and p(1x3) surface structures observed upon oxygen adsorption on a Mo(112) surface. The authors' simulations reveal an unusual flexibility of Mo(112) resulting in oxygen-induced reconstructions and lead to more stable structures than any suggested so far. Comparison of the stabilities of the predicted models shows that different p(1x2) and p(1x3) structures may coexist over a wide range of oxygen pressures. A pure p(1x2) structure can be obtained only in a narrow region of oxygen pressures. In contrast, a pure p(1x3) structure cannot exist as a stable phase. The results of simulations are fully supported by a multitude of experimental data obtained from low energy electron diffraction, x-ray photoelectron spectroscopy, and scanning tunneling microscopy.