The formation and structure of gas-phase vanadium oxide cluster anions are examined using a guided ion beam mass spectrometer coupled with a laser vaporization source. The dominant peaks in the anion total mass distribution correspond to clusters having stoichiometries of the form (VO2)(n)(VO3)(m)(O-2)(q)(-). Collision-induced dissociation studies of the vanadium oxide species V2O4-6-, V3O6-9-, V4O8-10-, V5O11-13-, V6O13-15-, and V7O16-18- indicate that VO2, VO3, and V2O5 units are the main building blocks of these clusters. There are many similarities between the anion mass distribution and that of the cation distribution studied previously. The principal difference is a shift to higher oxygen content by one additional oxygen atom for the stoichiometric anions (VxOy-) as compared to the cations with the same number of vanadium atoms, which is attributed to the extra pair of electrons of the anionic species. The oxygen-rich clusters, VxOy(O-2)(-), are shown to more tightly adsorb molecular oxygen than those of the corresponding cationic clusters. In addition, the bond dissociation thresholds for the vanadium oxide clusters DeltaE(V+-O)=6.09 +/-0.28 eV, DeltaE(OV+-O)=3.51 +/-0.36 eV, and DeltaE(O2V--O)=5.43 +/-0.31 eV are determined from the energy-dependent collision-induced dissociation cross sections with Xe as the collision partner. To the best of our knowledge, this is the first bond dissociation energy reported for the breaking of the V-O bond of a vanadium oxide anion.