Using first principle alloy theory, we calculate the basal stacking fault energies as a function of chemical composition for a series of Mg binary alloys by accounting for the chemical disorder in solid solution. We show that while the basal stacking fault energies significantly increase with the addition of Co, Ni, Ag, and Li, they obviously decline upon alloying with Sn, Y, Ca, and Al. In contrast, Zn and Ti exhibit negligible influence on the basal stacking fault energy of I1 and I2 fault. The varied influence of alloying species on basal stacking fault energies are demonstrated to predominately determined by the volume- and composition-dependent relative phase stability between face-centered cubic and hexagonal close-packed structure. The influence of alloy species predicted in solid solution are obviously different from those computed for segregated ones, underlining the significance of chemical disorder to the intrinsic energy barriers of Mg solid solutions.