The 3-dimensional (3D) atomic-scale structure of newly discovered face-centered cubic (fcc) and conventional hexagonal close packed (hcp) type ruthenium (Ru) nanoparticles (NPs) of 2.2 to 5.4 nm diameter were studied using X-ray pair distribution function (PDF) analysis and reverse Monte Carlo (RMC) modeling. Atomic PDF based high-energy X-ray diffraction measurements show highly diffuse X-ray diffraction patterns for fcc- and hcp-type Ru NPs. We here report the atomic-scale structure of Ru NPs in terms of the total structure factor and Fourier-transformed PDF. It is found that the respective NPs have substantial structural disorder over short- to medium-range order atomic distances from the PDF analysis. The first-nearest-neighbor peak analyses show a significant size dependence for the fcc-type Ru NPs demonstrating the increase in the peak height due to an increase in the number density as a function of particle size. The bond angle and coordination number (CN) distribution for the RMC-simulated fcc- and hcp-type Ru NP models indicated inherited structural features from their bulk counterparts. The CN analysis of the whole NP and surface of each RMC model of Ru NPs show the low activation energy packing sites on the fcc-type Ru NP surface atoms. Finally, our newly defined order parameters for RMC simulated Ru NP models suggested that the enhancement of the CO oxidation activity of fcc-type NPs was due to a decrease in the close packing ordering that resulted from the increased NP size. These structural findings could be positively supported for synthesized low-cost and high performance nano-sized catalysts and have potential application in fuel-cell systems and organic synthesis.