The growth scenario of monatomic wires on fcc (110) metal surfaces via intermixing of deposited and substrate atoms is reported. We present theoretical investigation of self-assembly of one-dimensional nanostructures during thermal deposition of Fe and Co atoms on Pd(110) in the submonolayer regime. Calculations performed by means of density-functional theory demonstrate that deposited atoms incorporate into the top-most substrate layer. Kinetic Monte Carlo simulations based on ab initio calculated diffusion barriers of relevant atomic processes indicate that surface diffusion of expelled atoms is responsible for growth of atomic wires consisting mainly of Pd atoms.