The shape of AuPd nanoparticles is engineered by surface stress relaxation, achieved by varying the Au content in nanoparticles of Pd-rich compositions. AuPd nanoparticles are grown in the gas phase for several compositions and growth conditions. Their structure is atomically resolved by HRTEM/STEM and EDX. In pure Pd distributions the dominant structures are FCC truncated octahedra (TO), while increasing the Au content there is a transition to icosahedral (Ih) structures in which Au atoms are preferentially placed at the nanoparticle surface. The transition is sharper for growth conditions closer to equilibrium. The physical origin of the transition is determined with the aid of computer simulations. Global optimization searches and free energy calculations confirm that Ih become the equilibrium structure for increasing the Au content. Atomic stress calculations demonstrate that the TO → Ih shape change is caused by a better relaxation of anisotropic surface stress in icosahedra.