The properties of hetero-nanocrystals (HNCs) depend strongly on the mutual arrangement of the nanoscale components. In this work we have investigated the structural and morphological evolution of colloidal PbSe/CdSe core/shell quantum dots upon annealing under vacuum. Prior to annealing the PbSe core has an approximately octahedral morphology with eight {111} facets, and the CdSe shell has zinc-blende crystal structure. Thermal annealing under vacuum at temperatures between 150 C and 200 C induces a structural and morphological reconstruction of the HNCs whereby the PbSe core and the CdSe shell are reorganized into two hemispheres joined by a common {111} Se plane. This thermally induced reconstruction leads to considerable changes in the optical properties of the colloidal PbSe/CdSe HNCs.