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 rthe development and application of two independent analyses to search for the signature of the NMO with three years of DeepCore data. 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. Both analyses show that the dataset is fully compatible with both mass orderings. For the more sensitive analysis, we observe a preference for Normal Ordering with a $p$-value of $p_\mathrm{IO} = 15.3\%$ and $\mathrm{CL}_\mathrm{s}=53.3\%$ for the Inverted Ordering hypothesis, while the experimental results from both analyses are consistent within their uncertainties. Since the result is independent of the value of $\delta_\mathrm{CP}$ and obtained from energies $E_ u \gtrsim 5\,\mathrm{GeV}$, it is complementary to recent results from long-baseline experiments. These analyses set the groundwork for the future of this measurement with more capable detectors, such as the IceCube Upgrade and the proposed PINGU detector.