Knowledge of nucleation and further growth of Bi2Se3 nanoplates on different substrates is crucial for obtaining ultrathin nanostructures and films of this material by physical vapour deposition technique. In this work, Bi2Se3 nanoplates were deposited under the same experimental conditions on different types of graphene substrates (as-transferred and post-annealed chemical vapour deposition grown monolayer graphene, monolayer graphene grown on silicon carbide substrate). Dimensions of the nanoplates deposited on graphene substrates were compared with the dimensions of the nanoplates deposited on mechanically exfoliated mica and highly ordered pyrolytic graphite flakes used as reference substrates. The influence of different graphene substrates on nucleation and further lateral and vertical growth of the Bi2Se3 nanoplates is analysed. Possibility to obtain ultrathin Bi2Se3 thin films on these substrates is evaluated. Between the substrates considered in this work, graphene grown on silicon carbide is found to be the most promising substrate for obtaining of 1-5 nm thick Bi2Se3 films.