Most salts raise the surface tension of water. Interpretation of this phenomenon via the Gibbs adsorption equation has led to the commonly held belief that the ions are repelled from the air/solution interface. Here, we report results from molecular dynamics simulations of a series of sodium halide solution/air interfaces. The simulations reproduce the experimentally measured increases in surface tension relative to pure water, Analysis of the structure reveals that the small, nonpolarizable fluoride anion is excluded from the interface, in accord with the traditional picture. However, all of the larger, polarizable halide anions are present at the interface, and bromide and iodide actually have higher concentrations in the interfacial region than in the bulk. On the basis of the simulations we develop a molecular picture of hydrogen bonding in the interfacial region that might be tested by surface sensitive spectroscopic experiments. The novel, microscopic view of the interfacial structure of aqueous salt solutions presented in this paper has implications for the reactivity of sea salt aerosols in the marine boundary layer, and bromine chemistry in the remote Arctic at polar sunrise.