A single-atom catalyst (SAC) that was first proposed by us in 2011 has aroused significant recent interest. Among the various SACs, FeO_x-based ones including Pt₁/FeO_x, Ir₁/FeO_x, Au₁/FeO_x, Ni₁/FeO_x, and Fe₁/FeO_x have been investigated either experimentally or theoretically for CO oxidation. However, a systematic study of FeOx-based SACs has not been conducted. For a comprehensive understanding of FeO_x-supported single-metal-atom catalysts, extensive density functional theory calculations were carried out on the activities and catalytic mechanisms of SACs with the 3d, 4d, and 5d metals of group VIII to IB, i.e., M₁/FeO_x (M = Fe, Co, Ni, Cu; Ru, Rh, Pd, Ag; Os, Ir, Pt, Au) for CO oxidation. Remarkably, a new noble metal SAC, Pd₁/FeO_x, with high activity in CO oxidation was found and is predicted to be even better than the previously reported Pt₁/FeO_x and Ni₁/FeO_x. In comparison, other M₁/FeO_x SACs (M = Fe, Co, Cu; Ru, Rh, Ag; Os, Ir, Au) showed only low activities in CO oxidation. Moreover, the adsorption strength of CO on the single-atom active sites was found to be the key in determining the catalytic activity of these SACs for CO oxidation, because it governs the recoverability of oxygen vacancies on their surfaces in the formation of a second CO₂ during CO oxidation. Our systematic studies of FeO_x-supported SACs will help in understanding the fundamental mechanisms of the interactions between singly dispersed surface metal atoms and FeOx substrate and in designing highly active FeO_x-supported SACs.