Self-organized alloying of Au with Rh in nanoclusters on an ordered thin film of Al2O3/NiAl(100) was investigated via various surface probe techniques under ultrahigh-vacuum conditions and calculations based on density-functional theory. The bimetallic clusters were formed on the sequential deposition of vapors of Au and Rh onto Al2O3/NiAl(100) at 300 K. The formation was more effective on the oxide seeded with Rh, since all post-deposited Au joined the pregrown Rh clusters; for metal deposition in the reverse order, some separate Rh clusters were formed. The contrasting behavior is rationalized through the easier nucleation of Rh on the oxide surface, due to the stronger Rh-oxide and Rh-Rh bonds. The alloying in the clusters proceeded, regardless of the order of metal deposition, toward a specific structure: an fcc phase, (100) orientation and Rh core-Au shell structure. The orientation, structural ordering and lattice parameters of the Au-Rh bimetallic clusters resembled Rh clusters, rather than Au clusters, on Al2O3/NiAl(100), even with Rh in a minor proportion. The Rh-predominated core-shell structuring corresponds to the binding energies in the order Rh-Rh > Rh-Au > Au-Au. The core-shell segregation, although active, was somewhat kinetically hindered, since elevating the sample temperature induced further encapsulation of Rh. The bimetallic clusters became thermally unstable above 500 K, for which both Rh and Au atoms began to diffuse into the substrate. Moreover, the electronic structures of surface elements on the bimetallic clusters, controlled by both structural and electronic effects, show a promising reactivity.