Rh is one of the most important noble metals for industrial applications. A major fraction of Rh is used as a catalyst for emission control in automotive catalytic converters because of its unparalleled activity toward NOx reduction. However, Rh is a rare and extremely expensive element; thus, the development of Rh alternative composed of abundant elements is desirable. Pd and Ru are located at the right and left of Rh in the periodic table, respectively, nevertheless this combination of elements is immiscible in the bulk state. Here, we report a Pd-Ru solid-solution-alloy nanoparticle (PdxRu1-x NP) catalyst exhibiting better NOx reduction activity than Rh. Theoretical calculations show that the electronic structure of Pd0.5Ru0.5 is similar to that of Rh, indicating that Pd0.5Ru0.5 can be regarded as a pseudo-Rh. Pd0.5Ru0.5 exhibits better activity than natural Rh, which implies promising applications not only for exhaust-gas cleaning but also for various chemical reactions.