PdxRu1-x solid solution alloy nanoparticles were successfully synthesized over the whole composition range through a chemical reduction method, although Ru and Pd are immiscible at the atomic level in the bulk state. From the XRD measurement, it was found that the dominant structure of PdxRu1-x changes from fcc to hcp with increasing Ru content. The structures of PdxRu1-x nanoparticles in the Pd composition range of 30-70% consisted of both solid solution fcc and hcp structures, and both phases coexist in a single particle. In addition, the reaction of hydrogen with the PdxRu1-x nanoparticles changed from exothermic to endothermic as the Ru content increased. Furthermore, the prepared PdxRu1-x nanoparticles demonstrated enhanced CO-oxidizing catalytic activity; Pd0.5Ru0.5 nanoparticles exhibit the highest catalytic activity. This activity is much higher than that of the practically used CO-oxidizing catalyst Ru and that of the neighboring Rh, between Ru and Pd.