Submonolayer deposition of 3d transition metals such as Cr, Mn, Fe, Co, and Ni on Pd(110) at room temperature causes the formation of monoatomic chains of Pd as identified with scanning tunneling microscopy and spectroscopy. In agreement with recent theoretical predictions [Phys. Rev. B 79, 155410 (2009)], the substitution of Pd substrate atoms with the deposited atoms of 3d metals is found to be responsible for the formation of Pd atomic chains. This finding clarifies the long-debated issue about the chemical composition of the atomic chains grown on Pd(110) and points out the intriguing processes in the formation of self-assembled and self-organized nanostructures.