Understanding the structure of bimetallic clusters is increasingly important due to their emerging practical applications. Herein we investigate the structure of 38-atom CuPd clusters using a genetic algorithm with cluster energies described by the semi-empirical Gupta potential. Selected clusters are then refined with density functional theory. Three different parameterisations of the Gupta potential are used and their performance assessed to understand what features of bulk and surfaces are necessary to capture for accurate description of small clusters. Three general regions of motif stability exist; for the Pd majority clusters (Pd38 to Cu4Pd34) the truncated octahedron is most stable, while for clusters of intermediate compositions (Cu5Pd33 to Cu25Pd13) a "pancake" icosahedron is most stable, and for the Cu majority clusters (Cu26Pd12 to Cu38) again the truncated octahedron is most stable. CuPd clusters tend to segregate to a Cu-core, Pd-shell structure if possible, and at higher Cu compositions, the Pd segregates to the faces of the cluster. Using multiple parameterisations of the Gupta potential ensures the full variety of possible structures is found, and improves the search for the most stable CuPd clusters.