Heterostructures of Bi2Se3 topological insulators were epitaxially grown on graphene by means of the physical vapor deposition at 500 °C. Micrometer-sized flakes with thickness 1 QL (quintuple layer ~ 1 nm) and films of millimeter-scale with thicknesses 2–6 QL had been grown on CVD graphene. The minimum thickness of large-scaled continuous Bi2Se3 films was found to be ~ 8 QL for the regime used. The heterostructures with a Bi2Se3 film thickness of > 10 QL had resistivity as low as 200–500 Ω/sq and a high room temperature carrier mobility ~ 1000–3400 cm2/Vs in the Bi2Se3/graphene interface channel. Moreover, the coexistence of a p-type graphene-related conductive channel, simultaneously with the n-type conductive surface channel of Bi2Se3, was observed. The improvement of the bottom Bi2Se3/graphene interface with the increase in the growth time clearly manifested itself in the increase of conductivity and carrier mobility in the grown layer. The grown Bi2Se3/G structures have lower resistivities and more than one order of magnitude higher carrier mobilities in comparison with the van der Waals Bi2Se3/graphene heterostructures created employing exfoliation of thin Bi2Se3 layers. The grown heterostructures demonstrated the properties that are perspective for new functional devices, for a variety of signal processing and logic applications.