Titanium dioxide/graphene composites have recently been demonstrated to improve the photocatalytic activity of TiO2 in visible light. To better understand the interactions of TiO2 with graphene we have investigated the growth of TiO2 nanoclusters on single-layer graphene/Ru(0001) using scanning tunneling microscopy (STM) and Auger electron spectroscopy (AES). Deposition of Ti in the O-2 background at 300 K resulted in the formation of nanoclusters nucleating on intrinsic defects in the graphene (Gr) layer. The saturation nanocluster density decreased as the substrate temperature was increased from 300 to 650 K, while deposition at 700 K resulted in the significant etching of the Gr layer. We have also prepared nanoclusters with Ti2O3 stoichiometry using lower O-2 pressures at 650 K. Thermal stability of the TiO2 nanoclusters prepared at 300 K was evaluated with AES and STM. No change in oxidation state for the TiO2 nanoclusters or etching of the Gr layer was observed up to similar to 900 K. Annealing studies revealed that cluster ripening proceeds via a Smoluchowski mechanism below 800 K. Above 800 K, the changes in cluster shapes indicate an onset of diffusion within the clusters. At even higher temperatures, the nanoclusters undergo reduction to TiOx (x approximate to 1-1.5) which is accompanied by oxidation and etching of the Gr. Our studies demonstrate that highly thermally stable TiOx nanoclusters of controlled composition and morphology can be prepared on Gr supports.