Atomic clusters are being actively studied for activation of methane, the most stable alkane molecule. While many cluster cations are very reactive with methane, the cluster anions are usually not very reactive, particularly for noble metal free anions. This study reports that the reactivity of molybdenum carbide cluster anions with methane can be much enhanced by adsorption of CO. The Mo2C2- is inert with CH4 while the CO addition product Mo2C3O- brings about dehydrogenation of CH4 under thermal collision conditions. The cluster structures and reactions are characterized by mass spectrometry, photoelectron spectroscopy, and quantum chemistry calculations, which demonstrate that the Mo2C3O- isomer with dissociated CO is reactive but the one with non-dissociated CO is unreactive. The enhancement of cluster reactivity promoted by CO adsorption in this study is compared with those of reported systems of a few carbonyl complexes.