Stoichiometric Cu2Se nanocrystals were synthesized in either cubic or hexagonal (metastable) crystal structures and used as the host material in cation exchange reactions with Pb2+ ions. Even if the final product of the exchange, in both cases, was rock-salt PbSe nanocrystals, we show here that the crystal structure of the starting nanocrystals has a strong influence on the exchange pathway. The exposure of cubic Cu2Se nanocrystals to Pb2+ cations led to the initial formation of PbSe unselectively on the overall surface of the host nanocrystals, generating Cu2Se@PbSe core@shell nanoheterostructures. The formation of such intermediates was attributed to the low diffusivity of Pb2+ ions inside the host lattice and to the absence of preferred entry points in cubic Cu2Se. On the other hand, in hexagonal Cu2Se nanocrystals, the entrance of Pb2+ ions generated PbSe stripes "sandwiched" in between hexagonal Cu2Se domains. These peculiar heterostructures formed as a consequence of the preferential diffusion of Pb2+ ions through specific (a, b) planes of the hexagonal Cu2Se structure, which are characterized by almost empty octahedral sites. Our findings suggest that the morphology of the nanoheterostructures, formed upon partial cation exchange reactions, is intimately connected not only to the NC host material, but also to its crystal structure.