Lead halide perovskite and chalcogenide heterostructures which share the ionic and covalent interface bonding may be the possible materials in bringing phase stability to these emerging perovskite nanocrystals. However, in spite of significant successes in the development of halide perovskite nanocrystals, their epitaxial heterostructures with appropriate chalcogenide nanomaterials have largely remained unexplored. Keeping the importance of these materials in mind, herein, epitaxial nanocrystal heterostructures of CsPbBr3-PbSe are reported. The shape remained rhombic dodecahedral-tetrahedral, and the phase retained orthorhombic-cubic for CsPbBr3 and PbSe nanocrystals, respectively. These are synthesized following the standard classical approach of heteronucleations of chalcogenide PbSe with CsPbBr3 perovskite nanostructures and characterized with high-resolution electron microscopic imaging. With an ultrafast study, the hot charge transfer from CsPbBr3 to PbSe is also established. As these are first of its kind nanostructures which are obtained with heteronucleation and growth of chalcogenides on halide perovskites, this finding is expected to open the roadmap for designing other heterostructures which are important for catalysis and photovoltaic applications.