The properties of Mo ultrathin films deposited on a TiO2(110) surface were investigated by scanning tunneling microscopy (STM) and spectroscopy (STS), as well as by Auger electron spectroscopy (AES). The substrate exhibited mainly large (1 x 1) terraces decorated by additional [001] rows (missing or added 1D structures) of reduced TiOx phases. Only a few percent of the surface exhibited a cross-linked (1 x 2) arrangement. The deposition of Mo layers at room temperature with a rate of approximately 0.4 monolayer/min resulted in nanoclusters of 1-2 nm with a low-profile shape (2D-like). Preferential decoration of the atomic steps was not found; at the same time, the 1D defect sites of missing or added rows on the (110) terraces were characteristically decorated by larger Mo nanocrystallites. This behavior indicates that the mobility of Mo atoms is higher on the more reduced regions of the substrate. The high dispersion of the Mo adlayer changed only slightly on annealing up to 700 K; in the range of 900-1050 K, however, a significant increase of the particle size accompanied by splitting of the TiO2(110) terraces was observed. This behavior may be explained by the partial oxidation of the supported Mo (accompanied by the reduction of the substrate) into tetragonal crystallites oriented and slightly elongated in the [001] or [110] direction of the TiO2(110) support. STS measurements indicated that the crystallites or the support/crystallite interface formed above 900 K possesses a wide band gap. The annealing above 1050 K resulted in the disappearance of Mo from the TiO2(110) surface, which may be explained by the formation and sublimation of MoO3 species at the perimeter of the nanoparticles. The change of AES signal intensities for O(KLL) and Mo(MNN) as a function of the annealing temperature also supports this mechanism.