We explore in detail the potential energy surfaces of the Al xMgy (x, y = 1-4) systems as case studies to test the utility and limitations of simple rules based on electron counts and the phenomenological shell model (PSM) for bimetallic clusters. We find that it is feasible to design stable structures that are members of this set of small Al-Mg binary clusters, using simple electron count rules, including the classical 4n + 2 Hückel model, and the most recently proposed PSM. The thermodynamic stability of the title compounds has been evaluated using several different descriptors, including the fragmentation energies and the electronic structure of the systems. Three stable systems emerge from the analysis: the Al 4Mg, Al2Mg2 and Al4Mg4 clusters. The relative stability of Al4Mg is explained by the stability of the Al4 2- subunit to which the Mg atom donates its electrons. Here the Mg2+ sits above the aromatic 10 π-electron Al4 2- planar ring. The Al2Mg 2 and Al4Mg4 clusters present more complicated 3D structures, and their stabilities are rationalized as a consequence of their closed shell nature in the PSM, with 10 and 20 itinerant electrons, respectively.