The structural stability of the prototypical complex Al12W structure, relative to the Cu3Au structure, is computed for Al compounds with 3d and 4d transition metals. The calculated structural energy differences are on the order of an eV per transition-metal atom, have their largest negative magnitude for the transition metals with nearly half-filled d bands, and have larger magnitudes for the 4d transition metals than for the 3d metals. These results suggest that electronic effects are more important than atomic-size effects. It is shown that a large part of the structural energy differences is due to the presence of a Fermi-level nonbonding peak in the electronic density of states (DOS) for the Cu3Au structure, which destabilizes that structure. The energy associated with the nonbonding peak has comparable contributions from a term in the energy that favors large unit-cell sizes, and from a local term that penalizes 90°bond angles around the transition-metal atoms. A significant additional contribution comes from the appearance of the dip in the DOS around the Fermi level for the Al12W structure. It is shown that the energetic factors developed here likely contribute to the relative stability of binary Altransition-metal icosahedral phases.