We report the first discovery of pure face-centered-cubic (fcc) Ru nanoparticles. Although the fcc structure does not exist in the bulk Ru phase diagram, fcc Ru was obtained at room temperature because of the nanosize effect. We succeeded in separately synthesizing uniformly sized nanoparticles of both fcc and hcp Ru having diameters of 2-5.5 nm by simple chemical reduction methods with different metal precursors. The prepared fcc and hcp nanoparticles were both supported on gamma-Al2O3, and their catalytic activities in CO oxidation were investigated and found to depend on their structure and size.