A detailed study is made of the structures and relative stabilities of nickel and aluminium clusters and nickel-aluminium "nanoalloy" clusters, with up to 55 atoms, modelled by the many-body Gupta potential. Random search and genetic algorithms are used to find the lowest energy isomers (both geometrical and permutational). For the pure Al and Ni clusters, the lowest energy structures are identical for most nuclearities but different structures are found for clusters with 15-18 atoms - the Al clusters having non-icosahedral structures. For these nuclearities, we investigate the effect of doping Al atoms into pure Ni clusters and vice versa, finding that the replacement of a single atom by a dopant atom is often sufficient to change the cluster geometry. The lowest energy isomers of nanoalloy clusters with the approximate composition "Ni3Al" generally have structures based on icosahedral packing, though truncated octahedral (fee packing) motifs are also observed. In agreement with previous studies, the atom ordering in the mixed Ni-Al clusters is found to depend on the maximization of the number of,Ni-Al interactions, the minimization of the cluster surface energy, and atom size effects.