By applying a genetic algorithm and ab initio atomistic thermodynamics, we identify the stable and metastable compositions and structures of Mg MOx clusters at realistic temperatures and oxygen pressures. We find that small clusters (M 5) are in thermodynamic equilibrium when x>M. The nonstoichiometric clusters exhibit peculiar magnetic behavior, suggesting the possibility of tuning magnetic properties by changing environmental pressure and temperature conditions. Furthermore, we show that density-functional theory with a hybrid exchange-correlation functional is needed for predicting accurate phase diagrams of metal-oxide clusters. Neither a (sophisticated) force field nor density-functional theory with (semi)local exchange-correlation functionals is sufficient for even a qualitative prediction. Published by American Physical Society. Published by the American Physical Society under the terms of the http://creativecommons.org/licenses/by/ 3.0/ Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.