Inspired by the recently discovered dynamics of single Fe atoms in graphene vacancies, we systemically examined the stable configurations, electronic structures, and catalytic activities of Fe-atom-embedded graphene substrates (including monovacancy graphene (MG) and divacancy graphene (DG)) by using first-principles calculations. We found that the doped Fe on the MG sheet (Fe/MG) is more stable than that on the DG sheet (Fe/DG). Doping with Fe atoms provides more transferred electrons to fill the vacancy defects of graphene and allows it to exhibit a more positive charge, which effectively regulates O₂ and CO adsorption. Also, the degree of interactions between the reactants and substrates are connected to the reaction pathways and energy barriers. For the Fe/MG sheet, the low coadsorption energy of gas molecules can promote the catalytic reaction through the Langmuir–Hinshelwood (LH) mechanism. In comparison, the initial step for CO oxidation on the Fe/DG sheet is through the Eley–Rideal (ER) mechanism, which is an energetically more favorable process. Moreover, the more stable Fe/MG sheet is a much more efficient catalyst for CO oxidation at low temperature, because the sequential reaction processes (LH and ER) have low enough energy barriers. These results provide valuable guidance on selecting the metal dopant in graphene materials to design effective atomic-scale catalysts.