Scanning tunneling microscopy (STM) completed by Anger-electron spectroscopy (AES) and thermal desorption spectroscopy (TDS) measurements was applied for investigating the formation and thermal-induced migration of carbon nanoclusters produced by the decomposition of CO on Rh/TiO2(110)-(1 x 2) planar catalyst. The annealing of a clean TiO2(110)-(1 x 2) surface in a CO atmosphere (few millibar pressure) at 500 K results in the reconstruction of the (1 x 2) structure into the (I x 4) arrangement. The same treatment of an Rh/TiO2(110)-(1 x 2) catalyst containing well-separated Rh nanocrystallites of approximately 10 nm in diameter leads to the formation of 3D carbon nanoclusters of 1-2 nm size. A fraction of the carbon formed on Rh nanoparticles diffuses (probably also in cluster form) onto the support already at 500 K (spillover). In the temperature range of 700-1100 K the carbon clusters agglomerate and collapse into larger nanoparticles. The accumulation of carbon on the existing Rh nanoparticles occurs at above 1100 K. Annealing at 1300 K causes the recovering of the original morphology of the Rh/TiO2 (110)-(1 x 2) catalyst, suggesting a total gasification of the surface carbon. These processes are accompanied by the oxidation of surface carbon by the bulk oxygen of titania resulting in the formation of CO in the temperature range 800-1300 K.