The ability to determine the atomic arrangement in nanoalloy catalysts and reveal the detailed structural features responsible for the catalytically active sites is essential for understanding the correlation between the atomic structure and catalytic properties, enabling the preparation of efficient nanoalloy catalysts by design. Herein we describe a study of CO oxidation over PdCu nanoalloy catalysts focusing on gaining insights into the correlation between the atomic structures and catalytic activity of nanoalloys. PdCu nanoalloys of different bimetallic compositions are synthesized as a model system and are activated by a controlled thermochemical treatment for assessing their catalytic activity. The results show that the catalytic synergy of Pd and Cu species evolves with both the bimetallic nanoalloy composition and temperature of the thermochemical treatment reaching a maximum at a Pd : Cu ratio close to 50 : 50. The nanoalloys are characterized structurally by ex situ and in situ synchrotron X-ray diffraction, including atomic pair distribution function analysis. The structural data show that, depending on the bimetallic composition and treatment temperature, PdCu nanoalloys adopt two different structure types. One features a chemically ordered, body centered cubic (B2) type alloy consisting of two interpenetrating simple cubic lattices, each occupied with Pd or Cu species alone, and the other structure type features a chemically disordered, face-centered cubic (fcc) type of alloy wherein Pd and Cu species are intermixed at random. The catalytic activity for CO oxidation is strongly influenced by the structural features. In particular, it is revealed that the prevalence of chemical disorder in nanoalloys with a Pd : Cu ratio close to 50 : 50 makes them superior catalysts for CO oxidation in comparison with the same nanoalloys of other bimetallic compositions. However, the catalytic synergy can be diminished if the Pd50Cu50 nanoalloys undergo phase segregation into distinct chemically-ordered (B2-type) and disordered (fcc-type) domains. This finding is significant since it provides a rational basis for streamlining the design and preparation of Pd-based nanoalloy catalysts in terms of atomic structure and phase state.