We investigated the structures and bonding of two series of early transition-metal oxide clusters, M2On- and M2On (M = Nb, To; n = 5-7) using photoelectron spectroscopy (PES) and density-functional theory (DFT). The stoichiometric M2O5 clusters are found to be closed shell with large HOMO-LUMO gaps, and their electron affinities (EM) are measured to be 3.33 and 3.71 eV for M = Nb and Ta, respectively; whereas EAs for the oxygen-rich clusters are found to be much higher: 5.35, 5.25, 5.28, and 5.15 eV for Nb2O6, Nb2O7, Ta2O6, and Ta2O7, respectively. Structural searches at the B3LYP level yield triplet and doublet ground states for the oxygen-rich neutral and anionic clusters, respectively. Spin density analyses reveal oxygen radical, diraclical, and superoxide characters in the oxygen-rich clusters. The M2O7 and M2O7 clusters, which can be viewed to be formed by M2O5-/0 + O-2, are utilized as molecular models to understand dioxygen activation on M2O5-and M2O5 clusters. The O-2 adsorption energies on the stoichiometric M2O5 neutrals are shown to be surprisingly high (1.3-1.9 eV), suggesting strong capabilities to activate O-2 by structural defects in Nb and Ta oxides. The PES data also provides valuable benchmarks for various density functionals (B3LYP, BP86, and PW91) for the Nb and Ta oxides.