The Neutrino Mass Ordering (NMO) remains one of the outstanding questions in the field of neutrino physics. One strategy to measure the NMO is to observe matter effects in the oscillation pattern of atmospheric neutrinos above $\sim 1\,\mathrm{GeV}$, as proposed for several next-generation neutrino experiments. Moreover, the existing IceCube DeepCore detector can already explore this type of measurement. We present results of a first search for the signature of the NMO with three years of DeepCore data based on two independent analyses. These analyses include a full treatment of systematic uncertainties and a statistically-rigorous method to determine the significance for the NMO from a fit to the data. For the more sensitive analysis, we o...