Recent experimental studies have demonstrated that short linear chains are often formed in the early stage of heteroepitaxy on the (111) noble metal surfaces at low temperatures. Here, we show that the surface-state mediated long-range interaction between adsorbates is the driving force for the self-organization of adsorbates at very low temperatures. Our kinetic Monte Carlo simulations for Co adatoms on Cu(111) and for Ce adatoms on Ag(111) reveal that these interactions can lead to the formation of linear chains.