Compounds CaAl2-xMgx (0 less than or equal to x less than or equal to 2) were synthesized and structurally characterized by X-ray diffraction experiments. With increasing Mg content x the sequence of Laves phase structures MgCu2 --> MgNi2 --> MgZn2 is revealed. The homogeneity ranges of the underlying phases were determined to be 0 less than or equal to x < 0.24(1) (MgCu2 type), 0.66(2) < x < 1.07(3) (MgNi2 type), and 1.51(5) < x less than or equal to 2.0 (MgZn2 type). Mg/Al site occupancies in CaAl1.34Mg0.66 and in CaAl0.44Mg1.56 were refined from neutron powder diffraction experiments and exposed a pronounced segregation of Al and Mg in MgNi2-type CaAl1.34Mg0.66 where Al atoms preferentially occupy the positions corresponding to trigonal bipyramids. In MgZn2-type CaAl0.44Mg1.56, however, the Mg/Al distribution was found to be nearly uniform. Structural stability in the quasi-binary system CaAl2-xMgx was investigated by first-principles calculations in which random occupational disorder of Mg and Al was modeled with the virtual crystal approximation. The theoretical calculations reproduced the experimental compositional stability ranges of the three different Laves phase structures very well. Structural changes in the quasi-binary system CaAl2-xMgx are induced by the electron concentration, which decreases with increasing x. The stability of the different Laves phase structures as a function of electron concentration was analyzed by the method of moments.