Using a combination of periodic, self-consistent, density functional theory (DFT) calculations and CO-stripping voltammetry experiments, we have designed a new class of Pt-M bimetallic monolayer catalysts supported on a non-Pt metal, which exhibit improved stability against CO poisoning and might be suitable for proton-exchange membrane fuel cell anodes. These surfaces help in reducing the overpotential associated with anodic CO oxidation and minimize the amount of Pt used, thereby reducing materials cost. DFT calculations predict highly repulsive interactions between adsorbed CO molecules on these surfaces, leading to weaker binding and lower coverage of CO than on pure Pt, which in turn facilitates oxidative removal of CO from these catalytic surfaces.