The thermodynamical stability of free, pristine gold clusters at finite temperature, and of cluster+ligands complexes at finite temperature and in the presence of an atmosphere composed of O2 and CO, is studied employing parallel tempering and ab initio atomistic thermodynamics. We focus on Au13, which displays a significant fluxional behavior: Even at low temperature (100 K) this cluster exhibits a multitude of structures that dynamically transform into each other. At finite temperature, the preference of this cluster for three-dimensional versus planar structures is found to result from entropic effects. For gold clusters containing one to four gold atoms in an O2 + CO atmosphere, we apply ab initio atomistic thermodynamics. On the basis of these considerations, we single out a likely reaction path for CO oxidation catalyzed by gold clusters.