We present an ab initio density functional theory study of the binding behavior of CO and O(2) molecules to two- and three-dimensional isomers of Au(13) in order to investigate the potential catalytic activity of this cluster towards low-temperature CO oxidation. First, we scanned the potential energy surface of Au(13) and studied the effect of spin-orbit coupling on the relative stabilities of the 21 isomers we identified. While spin-orbit coupling increases the stability of the three-dimensional more than the two-dimensional isomers, the ground state structure at 0 K remains planar. Second, we systematically studied the binding of CO and O(2) molecules onto the planar and three-dimensional structures lowest in energy. We find that the isomer dimensionality has little effect on the binding of CO to Au(13). O(2), on the other hand, binds significantly to the three-dimensional isomer only. The simultaneous binding of multiple CO molecules decreases the binding energy per molecule. Still, the CO binding remains stronger than the O(2) binding. We did not find a synergetic effect due to the co-adsorption of both molecular species. On the three-dimensional isomer, we find O(2) dissociation to be exothermic with an dissociation barrier of 1.44 eV.