The efficiency of PtSn alloy surfaces toward CO oxidation is demonstrated from first-principles theory. Oxidation kinetics based on atomistic density-functional theory calculations shows that the Pt3Sn surface alloy exhibits a promising catalytic activity for fuel cells. At room temperature, the corresponding rate outstrips the activity of Pt(111) by several orders of magnitude. According to the oxidation pathways, the activation barriers are actually lower on Pt3Sn(111) and Pt3Sn/Pt(111) surfaces than on Pt(111). A generalization of Hammer's model is proposed to elucidate the key role of tin on the lowering of the barriers. Among the energy contributions, a correlation is evidenced between the decrease of the barrier and the strengthening of the attractive interaction energy between CO and O moieties. The presence of tin modifies also the symmetry of the transition states which are composed of a CO adsorbate on a Pt near-top position and an atomic O adsorption on an asymmetric mixed PtSn bridge site. Along the reaction pathways, a CO2 chemisorbed surface intermediate is obtained on all the surfaces. These results are supported by a thorough vibrational analysis including the coupling with the surface phonons which reveals the existence of a stretching frequency between the metal substrate and the CO2 molecule.