The application of the ab initio genetic algorithm with an embedded gradient has been carried out for the elucidation of global minimum structures of a series of anionic sodium chloride clusters, NaxClx+1-(x=1-4), produced in the gas phase using electrospray ionization and studied by photoelectron spectroscopy. These are all superhalogen species with extremely high electron binding energies. The vertical electron detachment energies for NaxClx+1- were measured to be 5.6, 6.46, 6.3, and 7.0 eV, for x=1-4, respectively. Our ab initio gradient embedded genetic algorithm program detected the linear global minima for NaCl2- and Na2Cl3- and three-dimensional structures for the larger species. Na3Cl4- was found to have C-3v symmetry, which can be viewed as a Na4Cl4 cube missing a corner Na+ cation, whereas Na4Cl5- was found to have C-4v symmetry, close to a 3x3 planar structure. Excellent agreement between the theoretically calculated and the experimental spectra was observed, confirming the obtained structures and demonstrating the power of the developed genetic algorithm technique. (C) 2004 American Institute of Physics.