The structural and chemical changes of the GaAs(110) surface induced by sequential processes of UV/O-3 exposure, HF etching, and gas-phase polysulfide passivation were investigated by x-ray photoelectron spectroscopy (XPS), low-energy electron diffraction (LEED), and thermal desorption. Prior to any annealing, no samples showed any LEED patterns, and XPS indicated the presence of both As-S and Ga-S bonds. When the polysulfide-passivated surface was annealed to 400 degrees C, a sharp oblique LEED pattern started to emerge, which was accompanied by the desorption of S-As species. At the same time, XPS indicated that only a single type of sulfide (S-Ga) remained on the surface. Further annealing of the sample to 600 degrees C resulted in a complete removal of sulfur species from the surface and the appearance of a (2x1) LEED pattern. In contrast, no LEED pattern was observed from samples that had only been subjected to UV/O-3 treatment and HF etching up to an anneal temperature of 600 degrees C, thus indicating the absence of any kind of ordered structure on these surfaces. The results suggest that sulfide assisted the reordering of the GaAs(110) surface; this is most likely a crucial factor in the improvement of the electrical properties of the devices based on this surface.