It has been shown recently that while bulk gold is chemically inert, small Au clusters are catalytically active. The reasons for this activity and its dramatic dependence on cluster size are not understood. We use density functional theory to study O2 binding to Au clusters and to a Au(111) surface modified by adsorption of Au clusters on it. We find that O2 does not bind to a flat face of a planar Au cluster, even though it binds well to its edge. Moreover, O2 binds to Au clusters deposited on a Au(111) surface, even though it does not bind to Au(111). This indicates that a band gap is not an essential factor in binding O2, but surface roughness is. Adding electrons to the surface of a Au(111) slab, on which one has deposited a Au cluster, increases the binding energy of O2. However, adding electrons to a flat Ausurface has no effect on O2binding energy. These observations have a simple explanation: in clusters and in the rough surface, the highest occupied molecular orbital (HOMO) is localized and its charge density sticks out in the vacuum. This facilitates charge transfer into the π^* orbital of O2, which induces the molecule to bind to gold. A flat face of a cluster or a flat bulk surface tends to delocalize the HOMO, diminishing the ability of the surface to bind O2. The same statements are true for the LUMO orbital, which is occupied by the additional electron given to the system to charge the system negatively.