The catalytic oxidation of CO on Cu-embedded graphene is investigated by DFT. The reaction proceeds via a two-step mechanism of CO + O2 → OOCO → CO2 + O and CO + O → CO2. The energy barriers of the former are 0.25 and 0.54 eV, respectively, while the latter is a process with energetic drop. The high activity of Cu-embedded graphene may be attributed to the electronic resonance among electronic states of CO, O2, and the Cu atom, particularly among Cu-3d, CO-2π*, and O2-2π* orbitals. This good catalytic activity opens a new avenue to fabricate carbon-based catalysts for CO oxidation with lower cost and higher activity.