There is great interest in the study of topological insulator-based heterostructures due to expected emerging phenomena. However, a challenge of topological insulator (TI) research is the contribution of bulk conduction to the TI surface states. Both strain engineering and thickness control routes, which have been proposed to compensate for bulk doping, can be accessed through the use of nano-heterostructures consisting of topological insulator nanostructures grown on 2D materials. In this work, we report the synthesis of TI/graphene nano-heterostructures based on Bi2Te3 and Sb2Te3 nanoplatelets (NPs) grown on single-layer graphene. Various techniques were used to characterize this system in terms of morphology, thickness, composition, and crystal quality. We found that most of the obtained NPs are mainly <30 nm thick with thickness-dependent crystal quality, observed by Raman measurements. Thinner NPs (1 or 2 quintuple layers) tend to replicate the topography of the underlying single-layer graphene, according to roughness analysis. Finally, we show preliminary studies of their band structure obtained by Low Temperature Scanning Tunneling Microscopy, Scanning Tunneling Spectroscopy, and by Density Functional Theory. We observe a highly negative ED value which can be attributed to the presence of defects.