In this paper, a detailed density functional theory analysis of oxygen binding to Mg(0001) and subsequent clustering is presented. Oxygen monomer adsorption to Mg(0001) is demonstrated to be subsurface. It is shown that magnesium mediates an attractive oxygen-oxygen interaction which ultimately leads to the formation of hexagonal clusters of O* in the tetrahedral-1 site. The structure, work function, and binding properties of oxygen chemisorbed structures are compared with experiment, which allows the unique identification of the tetrahedral-1 site as the low coverage oxygen binding site and the construction of a picture of the early stages of oxide nuclei formation over magnesium. A model of oxide growth at O*/Mg(0001) is proposed. First-principles thermodynamics analysis is used to describe the surface oxide structures and reveals that surface oxides of intermediate oxygen coverage undergo spinodal decomposition. The thermodynamics of an underlying spinodal create an energetic driving force for decomposition of an oxide surface and renewal of a reactive metal interface that may be important in understanding magnesium corrosion. The implications of the findings are that magnesium unalloyed for oxide behavior will always be highly vulnerable to corrosion. DOI: 10.1103/PhysRevB.87.075450