Gold clusters on an iron-modified rutile TiO2(110) surface have been characterized via scanning tunneling microscopy and x-ray photoelectron spectroscopy. This study is focused on the impact of submonolayer preadsorbed Fe on the morphologies, surface compositions, and thermal stabilities of bimetallic Au-Fe systems by comparing them to elemental Au and Fe adsorbates. We found that a submonolayer gold adsorbate followed the nucleation mode of the iron precursor, which considerably enhanced the dispersion of nano-gold while improving its thermal stability. Finally, the temperature-programmed CO desorption spectra of Au and Au-Fe nanoparticles on TiO2(110) were compared.