The restructuring of S/W(111) surfaces has been studied using low-energy electron diffraction (LEED), Auger electron spectroscopy (AES) and scanning tunneling microscopy (STM). Dosing W(111) with a saturation coverage of H2S followed by annealing to > 800 K causes the substrate to reconstruct, forming a structure with (4 x 4) periodicity. In addition, the terrace-step configurations restructure and form triangular domains with a preferential orientation. These domains coalesce and enlarge, and also form multiple steps when the surface is heated to T > 1000 K. The low reactivity of sulfided W(111) to high exposures of oxygen demonstrates that the surface is passivated by sulfur. Adsorption of S onto a faceted Pd/W(111) surface causes the facets to disappear, restoring the surface's planar form upon annealing. The resulting features are dominated by a (2 x 2) structure. A size-mismatch mechanism, based on charge transfer between S/W and coadsorbed Pd/S on W, has been proposed to explain the formation of (4 x 4) and (2 x 2) structures, as well as the transition between these structures.