The structural phase transitions and the fundamental band gaps of Mg_xZn_1−xO alloys are investigated by detailed first-principles calculations in the entire range of Mg concentrateions x, applying a multiple-scattering theoretical approach (Korringa-Kohn-Rostoker method). Disordered alloys are treated within the coherent-potential approximation. The calculations for various crystal phases have given rise to a phase diagram in good agreement with experiments and other theoretical approaches. The phase transition from the wurtzite to the rock-salt structure is predicted at the Mg concentration of x=0.33, which is close to the experimental value of 0.33-0.40. The size of the fundamental band gap, typically underestimated b the local-density approximation, is considerably improved by the self-interaction correction. The increase in the gap upon alloying ZnO with Mg corroborates experimental trends. Our findings are relevant for applications in optical, electrical, and, in particular, in magnetoelectric devices.