NaSO4-(H2O)n (n = 0 - 4) clusters have been generated in the gas phase as model systems to simulate the first dissolution steps of sulfate salts in water. Photoelectron spectroscopy and theoretical calculation indicate that the first three water molecules strongly interact with both Na+ and SO42-, forming a three-water solvation ring to pry apart the Na+SO42- contact ion pair.