We present a systematic study of the structural changes of 19-atom PdnPt19-n nanoparticles as a function of composition, modeling the interatomic interactions with the many-body Gupta potential and using a genetic algorithm to obtain the lowest energy structures for all possible compositions. Topological analysis reveals that most of the structures are based on icosahedral packings and are strongly composition dependent. The pure Pd-19 nanoparticle exhibits a double icosahedral geometry, while the Ino decahedron is the basis of the Pt-19 cluster structure, which has a lower symmetry. Several structural motifs of the predicted lowest energy configurations are observed for bimetallic clusters in the range of compositions studied here. Six ideal structural families have been identified. Our results show that, for Pt-rich clusters, Pt atoms segregate into the core and the number of Pd-Pt bonds increases, while for Pd-rich clusters, the surface-segregated Pd atoms tend not to be nearest-neighbors. X-ray diffraction structure factors are simulated for all the predicted structures.