Using ab initio evolutionary simulations, we explore the entire range of possible stoichiometries for the Mg-O system at pressures of up to 850 GPa. In addition to MgO, our calculations find that two extraordinary compounds MgO 2 and Mg3O2 become thermodynamically stable at 116 GPa and 500 GPa, respectively. Detailed chemical bonding analysis shows large charge transfer in all magnesium oxides. MgO2 contains peroxide ions [O-O]2-, while non-nuclear electron density maxima play the role of anions in the electride compound Mg3O2. The latter compound is calculated to have a much narrower band gap compared to MgO and MgO2. We discuss the conditions under which MgO2 and Mg3O2 could exist in planetary interiors.