There are many reports of ZnSe nanowire synthesis, but photoluminescence measurements on these nanowires indicate weak band-edge and high sub-bandgap defect emission. The two main contributors to the non-optimal photoluminescence are nanowire growth at high temperatures and unpassivated surface states. In this paper, the synthesis of II-VI core-shell nanowires by metal organic vapor phase epitaxy is reported. We demonstrate that larger bandgap shells that passivate the nanowire surface states can be deposited around the nanowires by increasing the partial pressures of the shell reactants without a large increase in growth temperature, allowing high quality material to be obtained. The deposition of nearly lattice-matched ZnMgSSe shells on the ZnSe nanowires increases the band-edge luminescent intensity of the ZnSe nanowires by more than four orders of magnitude and improves the band-edge to defect photoluminescence intensity ratio to 12,000:1. The corresponding full widths at half maximum of the band-edge exciton peaks of the core-shell nanowires can be as narrow as 2.8 nm. It is also shown that magnesium and chlorine can be incorporated into the ZnSe nanowire cores, which shortens the emission wavelength and is known to act as an n-type dopant, respectively.