Vanadium oxide cluster anions (VmOn-)-O-16 and (VmOn-)-O-18 were prepared by laser ablation and reacted with hydrogen sulfide (H2S) in a fast flow reactor under thermal collision conditions. A time-of-flight mass spectrometer was used to detect the cluster distributions before and after the interactions with H2S. The experiments suggest that the oxygen-for-sulfur (O/S) exchange reaction to release water was evidenced in the reactor for most of the cluster anions: VmOn- + H2S -> VmOn-1S- + H2O. For reactions of clusters VO3- and VO4- with H2S, consecutive O/S exchange reactions led to the generation of sulfur containing vanadium oxide cluster anions VO3-kSk- (k = 1-3) and VO4-kSk- (k = 1-4). Density functional theory calculations were performed for the reactions of VO3-4- with H2S, and the results indicate that the O/S exchange reactions are both thermodynamically and kinetically favorable, which supports the experimental observations. The reactions of VmOn+ cluster cations with H2S have been reported previously (Jia, M.-Y.; Xu, B.; Ding, X.-L.; Zhao, Y.-X.; He, S.-G.; Ge, M.-F. J. Phys. Chem. C 2012, 116, 9043), and this study of cluster anions provides further new insights into the transformations of H2S over vanadium oxides at the molecular level.