We have carried Out a series of ab initio calculations to investigate changes in the structural and magnetic properties of pristine cobalt clusters upon CO chemisorption. Our results show that binding energies of CO to 13-55 atom (0.5-1.5 nm) cobalt nanoparticles and preferred chemisorption sites depend on the cluster structure (whether fcc or icosahedral), size, and surface coverage. In addition, we find a strong influence of CO on the magnetism of the cluster, leading to magnetic moments smaller than in the bulk, at variance with pristine Clusters which have magnetic moments larger than the bulk. Our findings suggest important changes in catalytic properties of cobalt at the nanoscale. Our theory suggests that at the nanoscale cluster size and surface coverage might control catalysis.