Combined experimental and ab initio studies show that the surface-state-mediated adatom-step and adatom-adatom interactions are the driving forces for the self-organization of Fe adatoms on vicinal Cu(111) surfaces at low temperatures. Our scanning tunneling microscope observations and the kinetic Monte Carlo simulations reveal the self-organization of Fe adatoms into atomic strings. The interatomic separation (1.2 nm) in the strings is not determined by the nearest-neighbor distance (0.26 nm) of the Cu atoms along the step edge but by the wavelength of the surface-state charge density oscillations.