XenI- van der Waals clusters have been investigated by anion zero electron kinetic energy (ZEKE) and partially discriminated threshold photodetachment (PDTP) spectroscopy. The experiments yield size-dependent electron affinities (EAs) and electronic state splittings between the X, I, and II states accessed by photodetachment. Cluster minimum energy structures have been determined by extensive simulated annealing molecular dynamics calculations using Xe-I(-) pair potentials from anion ZEKE spectroscopy and various nonadditive terms. The EAs calculated without many-body effects overestimate the experimental EAs by up to 3000 cm(-1). Repulsive many-body induction in the anion clusters is found to be the dominant nonadditive effect, though the attractive interaction between the iodide charge and the Xe-2 exchange quadrupole is also important. Unique global minimum energy structures for the anion clusters arise from the influence of the many-body terms, yielding, e. g., arrangements with a closed shell of xenon atoms around the iodide anion for the clusters with n = 12-14. The specific dependence of the EA curve on cluster size allows us to refine the absolute Xe-I bond lengths for the anion, X, I, and II state diatomic potentials to within +/-0.05 Angstrom.