The reactions of anionic metal clusters Mn- with O2 (M = V (n = 1-15), Cr (n = 1-15), Co (n = 1-12), and Ni (n = 1-14)) are investigated from 300 to 600 K using a selected-ion flow tube. All rate constants show a positive temperature dependence, well described by an Arrhenius equation. Rate constants exceed (or are extrapolated to exceed at higher temperatures) the Langevin-Gioumousis-Stevenson capture rate constant. Application of a capture model accounting for the finite size of the clusters reproduces the size-dependent trends in reactivity. The assumption that reactivity is further controlled by an energetic barrier early in the reaction coordinate is consistent with the experimental observations. An observed correlation of the derived barrier heights on the electron binding energy of Mn- suggests the barrier may be formed at an avoided crossing between electronic states correlating to Mn- + O2 and Mn + O2- reactants, analogous to that previously proposed for Aln- + O2 systems. The mechanism is analogous to that for reactions of O2 with neutral metal surfaces, indicating that gas-phase reactions of anionic metal clusters can be an appropriate model systems for surface oxidation.