We have studied the adsorption of NO on small Rh clusters, containing one to five atoms, using density functional theory in both spin-polarized and non-spin-polarized forms. We find that NO bonds more strongly to Rh clusters than it does to Rh(100) or Rh(111); however, it also quenches the magnetism of the clusters. This (local) effect results in reducing the magnitude of the adsorption energy, and also washes out the clear size-dependent trend observed in the non-magnetic case. Our results illustrate the competition present between the tendencies to bond and to magnetize, in small clusters.