The size-dependent reactivity of several transition-metal clusters: Con, Nbn, Rhn, and Wn with CO has been investigated in a cluster beam experiment. The reactions occur at single-collision-like conditions and the results are evaluated in terms of the reaction probability (S) in a collision. For all the four metals, clusters with more than 10 - 15 atoms show a high reaction probability, S >= 0.4, rather independent of size. For smaller Nbn and Wn, the reaction probability is lower, and for Nbn, large variations in the CO reactivity are observed in the n equals 8 - 13 range with a distinct minimum at Nb10. Using an LCAO approach within the local spin density approximation (LSDA) the adsorption of molecular CO on Nbn has also been investigated theoretically. The geometries of the bare clusters were optimized and two different sites for CO were investigated. The discussion is based on a detailed analysis of Nb4. The calculations show that compact structures with high coordination numbers are the most stable ones for the bare Nb clusters and hollow sites, also maximizing the coordination, are preferred for CO adsorption. The calculations indicate that a high CO-Nbn bond strength is obtained for clusters with a high density of states close to the Fermi level and for which the HOMO level has a symmetry that allows for an efficient back-donation of electrons to the 2(pi) *-orbital of CO. A particularly low chemisorption energy was calculated for the Nb10 cluster.