Gas-phase alkaline earth halide anions, MgX3- and CaX3- (X = Cl, Br), were produced using electrospray and investigated using photoelectron spectroscopy at 157 nm. Extremely high electron binding energies were observed for all species and their first vertical detachment energies were measured as 6.60 +/- 0.04 eV for MgCl3-, 6.00 +/- 0.04 eV for MgBr3-, 6.62 +/- 0.04 eV for CaCl3-, and 6.10 +/- 0.04 eV for CaBr3-. The high electron binding energies indicate these are very stable anions and they belong to a class of anions, called superhalogens. Theoretical calculations at several levels of theory were carried out on these species, as well as the analogous BeX3-. Vertical detachment energy spectra were predicted to compare with the experimental observations, and good agreement was obtained for all species. The first adiabatic detachment energies were found to be substantially lower (by about 1 eV) than the corresponding vertical detachment energies for all the MX3- species, indicating extremely large geometry changes between MX3- and MX3. We found that all the MX3- anions possess D-3h ((1)A(1)') structures and are extremely stable against dissociation into MX2 and X-. The corresponding neutral species MX3, however, were found to be only weakly bound with respect to dissociation toward MX2 + X. The global minimum structures of all the MX3 neutrals were found to be C-2v (B-2(2)), which can be described as (X-2(-))(MX+) charge-transfer complexes, whereas the (MX2X)-X-... (C-2v, B-2(1)) van der Waals complexes were shown to be low-lying isomers.