Ni-Al nanoparticles were fabricated from Ni3Al-based alloys using vacuum arc plasma evaporation, and their catalytic activities for carbon monoxide (CO) oxidation were examined. The synthesized nanopartides were characterized in detail using synchrotron radiation X-ray diffraction analyses, scanning transmission electron microscopy, and surface area measurements based on nitrogen adsorption. The as-fabricated nanoparticles were composed of Ni, Ni3Al, and a small amount of NiAl, with Al2O3 and NiO phases formed on their surfaces. The nanoparticles exhibited a much higher activity than that of a conventional atomized Ni3Al powder. It was found that the Ni phase is oxidized to NiO during CO oxidation, while the Ni3Al phase remains unchanged. It is likely that the NiO phase serves as the active species for CO oxidation, and the Ni3Al and Al2O3 phases serve as supports for the NiO phase.