Au, Rh, Pd, Au–Rh and Au–Pd nanoparticles (NPs) were synthesized by colloidal chemical reduction and immobilized on hydrothermally-prepared rutile titania nanorods. The catalysts were characterized by aberration-corrected TEM/STEM, XPS, and FTIR, and were evaluated in the hydrogenation of tetralin in the presence of H2S. Oxidizing and reducing thermal treatments were employed to remove the polyvinyl alcohol (PVA) surfactant. Reduction in H2 at 350 °C was found efficient for removing the PVA while preserving the size (ca. 3 nm), shape and bimetallic nature of the NPs. While Au–Pd NPs are alloyed at the atomic scale, Au–Rh NPs contain randomly distributed single-phase domains. Calcination–reduction of Au–Rh NPs mostly leads to separated Au and Rh NPs, while pre-reduction generates a well-defined segregated structure with Rh located at the interface between Au and TiO2 and possibly present around the NPs as a thin overlayer. Both the titania support and gold increase the resistance of Rh and Pd to oxidation. Furthermore, although detrimental to tetralin hydrogenation initial activity, gold stabilizes the NPs against surface sulfidation in the presence of 50 ppm H2S, leading to increased catalytic performances of the Au–Rh and Au–Pd systems as compared to their Rh and Pd counterparts.