We reveal the main mechanism of interface intermixing in the early stages of heteroepitaxy. Performing atomic scale calculations with ab-initio based many-body potentials, we show that submonolayer inclusions of Fe atoms in the topmost layer of Cu(001) observed in experiments are caused by a collective process of atomic exchanges near small embedded Fe islands. We demonstrate that mesoscopic relaxations in the substrate depend on the size of embedded islands and drastically affect site exchanges.