We report a joint experimental and theoretical investigation into the geometry, stability, and reactivity with oxygen of alloy metal clusters AlnMgm- (4 ≤ n+m ≤ 15; 0 ≤ m ≤ 3). Considering that Al and Mg possess three and two valence electrons, respectively, clusters with all possible valence electron counts from 11 to 46 are studied to probe the magic numbers predicted by the spherical jellium model, and to determine whether enhanced stability and reduced reactivity may be found for some AlnMgm- at non-magic numbers. Al5Mg2- and Al11Mg3- exhibit enhanced stability corresponding to the expected magic numbers of 20 and 40 electrons, respectively; while Al7Mg3-, Al11Mg-, and Al11Mg2- turn out to be unexpectedly stable at electron counts of 28, 36, and 38, respectively. The enhanced stability at non-magic numbers is explained through a crystal-field-like splitting of degenerate shells by the geometrical distortions of the clusters. AlnMgm- clusters appear to display higher oxidation than pure Aln- clusters, suggesting that the addition of Mg atoms enhances the combustion of pure aluminum clusters.