It is known experimentally that solid-state interdiffusion is substantially enhanced during plastic deformation. This is especially noticeable in Mechanical Alloying (MA) which is used for producing a wide range of metastable materials (supersaturated solid solutions, amorphous phases, nanostructures) with unique properties. However, a physical mechanism of enhanced diffusion during MA is not clearly understood yet, and a comprehensive model of this complex phenomenon has not been developed so far. Moreover, the role of the diffusion process in MA is hotly debated in literature. In this work a new, self-consistent mathematical model of solid-state interdiffusion in a binary substitutional system A-B during periodic plastic deformation is developed. The model includes basic physical factors that affect diffusion, such as generation of non-equilibrium point defects by gliding screw dislocations during deformation and their relaxation in periods between impacts. The cross-link terms are considered, and interaction of point defects with edge dislocations and incoherent phase boundary A/B is taken into account. Computer simulation is performed using realistic data (e.g., quasi-equilibrium self-diffusion coefficients known in literature) and the process parameters typical of MA in a vibratory mill. A repeated “deformation-rest” cycle is considered. The results of modeling reveal the physical mechanism of the enhancement of solid-state diffusion by periodic plastic deformation during MA and demonstrate that within the frame of this approach supersaturated solid solutions can form within a reasonably short processing time.