We report a computational investigation of CO adsorption on small nickel clusters that contain single impurity atoms H, C, or O. At bare Ni-4 and clusters with H or O impurity, the most stable coordination of the probe molecule is on top of a Ni atom which interacts with the impurity. The CNi4 cluster is an exception where 3-fold coordination of CO was determined to be more stable than that on top, however, by 4 kJ/mol only. Our results suggest that the heteroatoms X (X = H, C, O) affect only weakly the reactivity of the cluster with respect to CO; the binding energy of CO in the most stable complexes (CO)XNi4 increases at most by 10% compared to the value for bare Ni4, 194 kJ/mol. The impurity induces a small decrease of the CO infrared frequency shift for on-top coordinated CO, compared to Ni-4, because of partial oxidation of the metal moiety. A notable difference is predicted for clusters that contain a C impurity because of the different preferred coordination mode which results in a strong CO frequency red shift of similar to 300 cm(-1). The calculated characteristic CO frequency shifts may be helpful in identifying experimentally clusters with impurity atoms.