The structures of AgPd clusters supported on MgO(100) are investigated via a combination of global optimization searches within an atom-atom potential model and density-functional calculations. Although pure Ag and Pd clusters favor fcc structures in (100) epitaxy with the substrate, it is found that AgPd mixing creates a pocket of stability for polyicosahedral structures in the AgPd/MgO(001) nanoalloy phase diagram. Polyicosahedra are very stable for size around 40 atoms, where they compete with fcc(100) and decahedral structures. For clusters with up to 200 atoms and 50%-50% composition, these last two structural motifs are the most stable ones at the atom-atom potential level. For sizes of 400 atoms, fcc structures in (111) epitaxy with the substrate become close in energy to fcc(100) and Dh clusters, indicating a likely transition to (111) epitaxy for larger sizes.