Controlling the physical and chemical properties of alloy nanoparticles (NPs) is an important approach to optimize NP catalysis. Unlike other tuning knobs, such as size, shape, and composition, crystal structure has received limited attention and not been well understood for its role in catalysis. This deficiency is mainly due to the difficulty in synthesis and fine-tuning of the NPs' crystal structure. Here, Exemplifying by AuCu alloy NPs with face centered cubic (fcc) and face centered tetragonal (fct) structure, we demonstrate a remarkable difference in phase segregation and catalytic performance depending on the crystal structure. During the thermal treatment in air, the Cu component in fcc-AuCu alloy NPs segregates more easily onto the alloy surface as compared to that in fct-AuCu alloy NPs. As a result, after annealing at 250 degrees C in air for 1 h, the fcc- and fct-AuCu alloy NPs are phase transferred into Au/CuO and AuCu/CuO core/shell structures, respectively. More importantly, this variation in heterostructures introduces a significant difference in CO adsorption on two catalysts, leading to a largely enhanced catalytic activity, of AuCu/CuO NP catalyst for CO oxidation. The same concept can be extended to other alloy NPs, making it possible to fine-tune NP catalysis for many different chemical reactions.