The structural phase transitions and the fundamental band gaps of Mg(x)Zn(1-x)O alloys are investigated by detailed first-principles calculations in the entire range of Mg concentrations x, applying a multiple-scattering theoretical approach (Korringa-Kohn-Rostoker method). Disordered alloys are treated within the coherent potential approximation (CPA). 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 by the local density approximation, is considerably improved by the self-interaction correction. The increase of 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.