Well-aligned ZnO nanowire arrays have been prepared, and p-MgZnO has been deposited onto the nanowires to form core-shell heterostructures. Transmission electron microscopy confirms the formation of n-ZnO/p-MgZnO core-shell nanowire heterostructures. Under injection of a continuous current, random lasing with a threshold current of around 15 mA has been observed from the heterostructures. The low threshold may be due to the relatively high crystalline quality of the ZnO nanowires as well as the carrier confinement in the heterostructures.