Indium phosphide quantum dots (QDs) have drawn attention as alternatives to cadmium- and lead-based QDs that are currently used as phosphors in lamps and displays. The main drawbacks of InP QDs are, in general, a lower photoluminescence quantum yield (PLQY), a decreased color purity, and poor chemical stability. In this research, we attempted to increase the PLQY and stability of indium phosphide QDs by developing lattice matched InP/MgSe core-shell nanoheterostructures. The choice of MgSe comes from the fact that, in theory, it has a near-perfect lattice match with InP, provided MgSe is grown in the zinc blende crystal structure, which can be achieved by alloying with zinc. To retain lattice matching, we used Zn in both the core and shell and we fabricated InZnP/Zn_xMg_1-xSe core/shell QDs. To identify the most suitable conditions for the shell growth, we first developed a synthesis route to Zn_xMg_1-xSe nanocrystals (NCs) wherein Mg is effectively incorporated. Our optimized procedure was employed for the successful growth of Zn_xMg_1-xSe shells around In(Zn)P QDs. The corresponding core/shell systems exhibit PLQYs higher than those of the starting In(Zn)P QDs and, more importantly, a higher color purity upon increasing the Mg content. The results are discussed in the context of a reduced density of interface states upon using better lattice matched Zn_xMg_1-xSe shells.