The interaction Of O-2 with charged and neutral gold clusters, Au-N(-) and Au-N containing up to eight atoms, investigated through the use of density functional theory with generalized gradient corrections and scalar relativistic pseudopotentials, exhibits a pronounced sensitivity to the cluster size and to its charge state. Molecular adsorption is found to be favorable regardless of the charge state for clusters with N less than or equal to 3, while dissociative adsorption is favored for larger clusters. The dissociation process involves a significant barrier (I eV or more), and it is predicted to result in a large structural distortion in the host gold cluster. The interaction energy is largest for the anionic gold clusters where it exhibits an odd-even alternation as a function of the number of gold atoms, with the maxima occurring for AuNO2- complexes with even N. The molecular bonding mechanism to these complexes involves charge transfer to the oxygen molecule with a concomitant activation of the O-O bond to a superoxo-like state.