Self-consistent periodic density functional theory calculations (GGA-PW91) have been performed to study the adsorption of O and O-2 and the dissociation of O-2 on the (111) facets of ordered Pt3Co and Pt3Fe alloys and on monolayer Pt skins covering these two alloys. Results are compared with those obtained on two Pt(111) surfaces, one at the equilibrium lattice constant and the other laterally compressed by 2% to match the strain in the Pt alloys. The absolute magnitudes of the binding energies of O and O-2 follow the same order in the two alloy systems: Pt skin < compressed Pt(111) < Pt(111) < Pt3CO(111) or Pt-3-Fe(111). The reduced activity of the compressed Pt(111) and Pt skins for oxygen can be rationalized as being due to the shifting of the d-band center increasingly away from the Fermi level. We propose that an alleviation of poisoning by O and enhanced rates for reactions involving O may be some of the reasons why Pt skins are more active for the oxygen reduction reaction in low-temperature fuel cells. Finally, a linear correlation between the transition-state and final-state energies of O-2 dissociation on monometallic and bimetallic surfaces is revealed, pointing to a simple way to screen for improved cathode catalysts.