Density functional theory in combination with genetic algorithm is applied to determine the atomic models of p(1×2) and p(1×3) 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(1×2) and p(1×3) structures may coexist over a wide range of oxygen pressures. A pure p(1×2) structure can be obtained only in a narrow region of oxygen pressures. In contrast, a pure p(1×3) 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.