Polynary single-atom structures can provide synergistic functions based on multiple active sites and reactants, which significantly improve their catalytic performance. However, the structure-activity relationships of these special structures remain elusive. Here, we report atomically dispersed Fe-Ni dual-metal catalysts anchored on N-doped graphene as an efficient catalyst for CO oxidation. The density functional theory (DFT) calculation results show that Ni serves as a catalytic nucleophilic center for CO adsorption, whereas Fe serves as an electrophilic center for O2 adsorption, making full use of the dual-metal active sites. Thus, a heteronuclear Fe1Ni1@NGr catalyst with the synergistic effect of combining dissimilar metal atoms has better catalytic activity and lower propensity for CO poisoning than its homonuclear counterparts. Comparing the Langmuir-Hinshelwood (LH) and Eley-Rideal (ER) mechanisms for CO oxidation on Fe1Ni1@NGr, Ni2@NGr, and Fe2@NGr, we find that the LH mechanism with coadsorbed CO and O2 is dynamically more favorable. In addition, residual oxygen atoms attached to the Fe-Ni active sites can easily react with additional CO molecules, indicating the achievement of a high recycling rate. These findings reveal a synergistic catalytic mechanism of graphene-supported atomically dispersed transition dual-metal catalysts, providing important guidance for the rational design of atomically dispersed catalysts.