Atomic diffusion is at the basis of chemical ordering transformations in nanoalloys. Understanding the diffusion mechanisms at the atomic level is therefore a key issue in the study of the thermodynamic behavior of these systems and, in particular, of their evolution from out-of-equilibrium chemical ordering types often obtained in the experiments. Here, the diffusion is studied in the case of a single-atom impurity of Ag or Au moving within otherwise pure magic-size icosahedral clusters of Cu or Co by means of two different computational techniques, i.e., molecular dynamics and metadynamics. Our simulations reveal unexpected diffusion pathways, in which the displacement of the impurity is coupled with the creation of vacancies in the central part of the cluster. We show that the observed mechanism is quite different from the vacancy-mediated diffusion processes identified so far, and we demonstrate that it can be related to the presence of non-homogeneous compressive stress in the inner part of the icosahedral structure.