The long-range ordered surface alloy Bi/AG(111) is found to exhibit a giant spin splitting of its surface electronic structure due to spin-orbit coupling, as is determined by angle-resolved photoelectron spectroscopy. First-principles electronic structure calculations fully confirm the experimental findings. The effect is brought about by a strong in-plane gradient of the crystal potential in the surface layer, in interplay with the structural asymmetry due to the surface-potential barrier. As a result, the spin polarization of the surface states is considerably rotated out of the surface plane.