Controlled synthesis of a hybrid nanomaterial based on titanium oxide and single-layer graphene (SLG) using atomic layer deposition (ALD) is reported here. The morphology and crystallinity of the oxide layer on SLG can be tuned mainly with the deposition temperature, achieving either a uniform amorphous layer at 60 °C or ∼2 nm individual nanocrystals on the SLG at 200 °C after only 20 ALD cycles. A continuous and uniform amorphous layer formed on the SLG after 180 cycles at 60 °C can be converted to a polycrystalline layer containing domains of anatase TiO2 after a postdeposition annealing at 400 °C under vacuum. Using aberration-corrected transmission electron microscopy (AC-TEM), characterization of the structure and chemistry was performed on an atomic scale and provided insight into understanding the nucleation and growth. AC-TEM imaging and electron energy loss spectroscopy revealed that rocksalt TiO nanocrystals were occasionally formed at the early stage of nucleation after only 20 ALD cycles. Understanding and controlling nucleation and growth of the hybrid nanomaterial are crucial to achieving novel properties and enhanced performance for a wide range of applications that exploit the synergetic functionalities of the ensemble.