The construction of topological insulator/superconductor heterostructures attracts a lot of interest because of its potential to realize artificial topological superconductors hosting Majorana fermions. By means of molecular beam epitaxy, high-quality thin films of a topological insulator, Bi2Se3, can be grown on a superconductor substrate, 2H-NbSe2(0001), with an atomically smooth interface. To ascertain the atomic structure of the Bi2Se3/NbSe2 heterostructure, the initial growth stage was investigated with a scanning tunneling microscope (STM). In the growth process, we found that Bi atoms were first deposited to form a single Bi(110) bilayer, which is revealed to stand nearly freely on the NbSe2 surface and exhibits various moiré patterns. In the formation of the first quintuple layer of Bi2Se3 by co-depositing Bi and Se atoms, the Bi(110) bilayer transits to a BiSe interfacial layer, which effectively reduces the large lattice mismatch between Bi2Se3 and NbSe2 . Based on atomic-resolution STM images and first-principles calculations, a NaCl-type structural model is proposed for the BiSe interfacial layer, on which Bi2Se3 thin films grow well in a layer-by-layer mode.