We determine the geometry of the ground state and of several low energ
y metastable configurations of oxygen adsorbed on Mg(0001) for coverag
e 1/16 less than or equal to Theta less than or equal to 1. In agreeme
nt with experiments, we find that oxygen is adsorbed below the Mg surf
ace, forming ionic islands commensurate with the metal lattice. Molecu
lar dynamics simulations show how O-2/Mg(0001) spontaneously dissociat
es and incorporates below the Mg top layer. The collision and the prog
ression towards the most stable configuration involve complex, many-at
om processes.