Co-doped Au25 nanoclusters with different numbers of doping atoms were synthesized and supported on CeO2. The catalytic properties were studied in the CO oxidation reaction. In all cases, an enhancement in catalytic activity was observed compared to the pure Au25 nanocluster catalyst. Interestingly, a different catalytic performance was obtained depending on the number of Co atoms within the cluster. This was related to the mobility of atoms within the cluster’s structure under pretreatment and reaction conditions, resulting in active CoAu nanoalloy sites. The evolution of the doped Au clusters into nanoalloys with well-distributed Co atoms within the Au cluster structure was revealed by combined XAFS, DRIFTS, and XPS studies. Overall, these studies contribute to a better understanding of the dynamics of doped nanoclusters on supports upon pretreatment and reaction, which is key information for the future development and application of bimetallic nanocluster (nanoalloy) catalysts.