This paper reports on the preparation and characterization of nanostructured Re and Co-Re/Al2O3/NiAl(110) surfaces designed as model catalysts for operando studies of Fischer-Tropsch synthesis. Scanning tunneling microscopy on pure Re particles identified strong Re-Al2O3 support interaction, resulting in uniform nucleation and growth on random point defects. X-ray photoelectron spectroscopy confirmed the strong interaction through a shift in the binding energy, in addition to size-dependent final state effects. Co-Re particles were prepared by sequential deposition of the two metals, resulting in core-shell structures in which the shell was (strongly) enriched with the metal deposited second. Annealing of bimetallic particles allowed for elemental redistribution, as was concluded from the XPS data and supported by modeling. The annealing also resulted in sintering of bimetallic clusters. Interestingly, the thermal stability of the Co-Re surfaces prepared by sequential deposition of Co, followed by Re, was better than that of both pure Co and pure Re.