The strong metal-oxide interaction of platinum nanoparticles (PtNPs) deposited on two types of cobalt oxides, CoO and Co3O4, was investigated using CO oxidation. Two different sizes of PtNPs as well as arc-plasma-deposited (APD) PtNPs without a capping layer were used to reveal the effect of metal-oxide interfaces on catalytic activity. An enhanced catalytic activity was observed on the PtNPs on the Co3O4 substrate, which was ascribed to the reducible support and to the interfacial sites.