Interactions of anions with hydrophobic surfaces of proteins and water-soluble polymers depend on the ability of the ions to shed their hydration shells. At positively charged surfactant monolayers, the interactions of anions are less well understood. Due to the interplay of electrostatic surface forces, hydration effects, and ion-ion interactions in the electrostatic double layer, a comprehensive microscopic picture remains elusive. Herein, we study the interactions of chloride, bromide, and a mixture of these two anions at the aqueous interface of dihexadecyldimethylammonium (DHDA+) and dioctadecyldimethylammonium (DODA+) cationic monolayers. Using molecular dynamics simulations and three surface-sensitive X-ray scattering techniques, we demonstrate that bromide interacts preferentially over chloride with both monolayers. The structure of the two monolayers and their interfacial electron density profiles obtained from the simulations quantitatively reproduce the experimental data. We observe that chloride and bromide form contact ion pairs with the quaternary ammonium groups on both monolayers. However, ion pairing with bromide leads to a greater reduction in the number of water molecules hydrating the anion, resulting in more energetically stable ion pairs. This leads to long-range (>3 nm) lateral correlations between bromide ions on the structured DODA+ monolayer. These observations indicate that ion hydration is the dominant factor determining the interfacial electrolyte structure.