Gas-phase reactivity of pure and partially oxidized tungsten atomic and cluster cations, W-n(+) (n = 1-6) and WnOm+ (n = 1-5, m <= 6), with methane is studied at the collision energies from 0.1 to 1.0 eV under single collision conditions. The dehydrogenation of CH4 (i.e., the release of H-2) is observed for most of WnOm+, whereas W-n(+) (n >= 2) are almost unreactive. This result indicates that the reactivity of tungsten clusters can be enhanced by the addition of oxygen atoms. Moreover, the reaction cross section of WnOm+ strongly depends on the cluster composition, and some clusters such as W2O3+, W-3(O)+, W3O5+, and W5O3+ exhibit high reactivity. It turns out that the reactivity of these clusters is roughly comparable to that of the typical platinum cluster cations, which are one of the most reactive clusters toward methane dehydrogenation. The reactivity of W-n(+) and WnOm+ toward CH4 can be explained by a simple model of their orbital energies and the potential energy diagrams obtained by using the density functional theory calculations. The calculations also suggest that the oxygen atom(s) in WnOm+ is like a spectator and the formation of a hydroxyl group is not necessary for the cleavage of C-H bonds in CH4.