Despite numerous efforts performed on the elimination of toxic gases from the air, the oxidation of carbon monoxide (CO) with metal-embedded nanostructures still remains a challenge. The geometry, electronic structure and catalytic properties of Pd-doped gra- phene (Pd-graphene) are investigated by means of density functional theory (DFT) cal- culations. The large atomic radius of Pd dopant in graphene can induce the local surface curvature and modulate the electronic structure of the sheet through the charge redis- tribution effects. Also, Pd-graphene can facilitate the O2 adsorption. Therefore, the catalytic activity of the Pd-graphene for CO oxidation reaction is enhanced. Moreover, the complete CO oxidation reactions on the Pd-graphene include a two-step process of the Langmuir- Hinshelwood (LH) reaction, in which the first step is almost barrier-less (Eact ¼ 0.002 eV) and the second step exhibits an energy barrier of 0.2 eV. The results indicate that the surface activity of graphene-based materials can be drastically improved by introducing the Pd dopants, so Pd-graphene can be a clue for fabricating graphene- based catalysts with high activity toward the oxidation of CO molecule.