Nanowire heterostructures, combining multiple phases within a single nanowire, modify functional properties and offer a platform for novel device development. Here, ZnO/ZnMgO core-shell nanowires are grown by molecular beam epitaxy. At growth temperatures above 750 °C, Mg diffuses into ZnO making heterostructure growth impossible; at lower shell-growth temperatures (500 °C), the core-shell structure is retained. Even very thin ZnMgO shells show increased intensity photoluminescence (PL) across the ZnO band-gap and a suppression in defect-related PL intensity, relative to plain ZnO nanowires. EDX measurements on shell thickness show a correlation between shell thickness and core diameter which is explained by a simple growth model.