The enhanced stability and modified electronic structure of intermetallic compounds provide discovery of superior catalysts for chemical conversions with high activity, selectivity, and stability. We find that the intermetallic NaAu2 is an active catalyst for CO oxidation at low temperatures. From density functional theory calculations, a reaction mechanism is suggested to explain the observed low reaction barrier of CO oxidation by NaAu2, in which a CO molecule reacts directly with an adsorbed O2 to form an OOCO* intermediate. The presence of surface Na increases the binding energy of O2 and decreases the energy barrier of the transition states.