Femtosecond, time-resolved photoelectron spectroscopy is used to investigate the dissociation dynamics of mass-selected anionic molecular-oxygen clusters. The observed transient photoelectron signal for the clusters (O-2)(n)(-) (n=3-5) shows the O-2(-) production; for n=1 and 2, we observe no time-dependence at this wavelength of 800 nm. The observed transients are bi-exponential in form with two distinct time constants, but with clear trends, for all investigated cluster sizes. These striking observations describe the reaction pathways of the solvated core and we elucidate two primary processes: Charge transfer with concomitant nuclear motion, and direct dissociation of the O-4(-) core-ion via electron recombination; the former takes 700-2700 fs, while the latter is on a shorter time scale, 110-420 fs. Both rates decrease differently upon increasing cluster size, indicating the critical role of step-wise solvation.