Exploring the unique catalytic properties of gold clusters associated with specific nano-architectures is essential for designing improved catalysts with a high mass-specific activity. We investigate the geometric and electronic structure of hexadecagold clusters in which Rh was doped. Density functional theory calculations demonstrate that the resulting neutral and negatively charged Rh-doped Au16 clusters are stable and bind CO and O2 stronger than Au16. Consequently, activation barriers for CO oxidation are lowered. Microkinetics simulations predict especially negatively charged Rh-doped Au16 clusters to exhibit very high CO oxidation activity, already at sub-ambient temperature. Our findings highlight the promise of alloying gold clusters with more reactive transition metals and the importance of charge transfer from the support in heterogeneous gold systems in catalyzing CO oxidation.