The anion photoelectron (PE) spectra of small mass-selected vanadium oxide clusters VnOm- (n = 4-15; m = 0-2) are measured at a fixed photon energy of 4.66 eV with the aid of a magnetic bottle photoelectron spectrometer. Cluster anions are generated in a pulsed laser vaporization cluster source. The electronic structure of VnOm- clusters is investigated as a function of size n and composition m with special regard to the increasing oxidation state. The addition of one or two oxygen atoms to the vanadium cluster core induces a change of the electronic structure in the near-threshold binding energy region below 2 eV. Main spectral features are contributed from the transition metal d-derived orbitals, whereas the oxygen 2p contribution induces a hybridization between vanadium and oxygen frontier orbitals in the entire series of the investigated clusters n = 4-15. Generally, electron affinities and vertical detachment energies increase with increasing cluster size revealing size-dependent discontinuities. Furthermore, relative dissociation energies for different oxygen-loss channels from the parent VnOm- clusters are determined from thermochemical cycles, and first insights into the stability patterns of neutral and negatively charged vanadium oxide clusters are provided.