We report on experiments probing the reactivity of neutral Au(n) clusters, n = 9-68, with carbon monoxide. The gold clusters are produced in a pulsed laser vaporization cluster source, operated at room temperature (RT) or at liquid-nitrogen temperature (LNT), pass through a low-pressure reaction cell containing CO gas, and are subsequently laser ionized. The reaction probabilities are determined by recording mass abundance spectra with time-of-flight mass spectrometry. The main observations are a strong temperature dependence and a remarkable size dependence. Upon cooling of the cluster source to LNT, the reactivity increases substantially. At LNT, the reaction probabilities for Au(n) with the first CO molecule are about a factor 10 higher than at RT. Moreover, adsorption of two, three, and even four CO molecules is observed, in contrast to RT clusters which at most adsorb one CO molecule. This temperature dependence is related to the lifetime of the cluster-molecule complexes, being much longer for cold clusters. The observed striking size dependence is similar at both temperatures and is discussed in terms of the electronic structure effects.