We have performed periodic first-principles calculations to examine the catalytic activity of B-doped graphene in oxidation of CO to CO2. It is found that B atoms of B-doped graphene can provide active sites to adsorb CO and O2 molecules. Based on our results, the termolecular Eley-Rideal (TER) pathway is the most energetically relevant mechanism for the CO + O2 reaction. Compared with the single noble-metal catalysts, B-doped graphene exhibits exceptional catalytic performance to oxidize CO molecules at normal temperatures. The findings can provide guidelines for designing active metal-free catalysts by doping of graphene.