We report a comprehensive experimental and theoretical study of the effect of oxidizing a TiO2(110) surface at moderate temperatures. The surfaces are investigated with scanning tunneling microscopy (STM), low-energy He+ ion scattering (LEIS) and static secondary ion mass spectroscopy (SSIMS). Flat(1 x 1)-terminated TiO2(110) surfaces are obtained by sputtering and annealing in UHV at 880 K. These surfaces are exposed to oxygen gas at elevated temperatures in the range 470-830 K. Formation of irregular networks of pseudo-hexagonal rosettes (6.5 Angstrom x 6 Angstrom) and small (1 (1) over bar 0] oriented (1 x 1) islands along with {001}-oriented strands is induced at temperatures from 470 to 660 K. After annealing above 830 K, only regular (1 x 1) terraces and white strands are observed. The composition of these oxygen-induced phases is quantified using O-18(2) gas in combination with LEIS and SSIMS measurements. The dependence of the restructuring process on annealing time, annealing temperature, and sample history is systematically investigated. Exposure to (H2O)-O-18 and air in the same temperature regime fails to induce the restructuring. UHV annealing of restructured, oxygen-enriched TiO2(110) surface smooths the surfaces and converts the rosette networks into strands and finally into the regular (1 x 1) terraces. This is reported in an accompanying paper [M. Li, W. Hebenstreit, U. Diebold, Phys. Rev. B (1999), submitted]. The rosette model is supported by first-principles density functional calculations which show a stable structure results, accompanied by significant relaxations from bulk-truncated positions. A mechanism for the dynamic processes of the formation of rosettes and (1 x 1) islands is presented and the importance of these results for the surface chemistry of TiO2(110) surfaces is discussed. (C) 1999 Elsevier Science B.V. All rights reserved.