Understanding the structure and composition of nanosized gold-copper (AuCu) clusters is crucial for designing an effective AuCu catalyst. Global optimization of AuCu clusters using atomistic force fields is a viable solution for clusters with at least a few nm sizes, because of its fast computation. Here we develop an atomistic many-body potential for AuCu on the basis of the second-moment approximation to the tight-binding model. We show that our potential is in good agreement with density-functional theory calculations, and use it to study the structure and chemical ordering of clusters of sizes up to ∼4 nm by means of global optimization searches. We show that the clusters present a surface enrichment in Au, while subsurface and central sites are enriched in Cu. Surface enrichment in Au and center enrichment in Cu are stronger in icosahedra. Surface Cu atoms prefer terrace sites on (111) facets. Both atomistic and DFT calculations show that L10 and L12 ordered phases are not favorable, even at their ideal compositions for these sizes, because of the tendency of Au to surface segregation. The stability range of icosahedral structures is wider in AuCu nanoalloys than in Au and Cu pure clusters.