Neutrinos mix and have mass differences, so decays from one to another must occur. But how fast? The best direct limits on non-radiative decays, based on solar and atmospheric neutrinos, are weak, $tau gtrsim 10^{-3}$ s ($m$/eV) or much worse. Greatly improved sensitivity, $tau sim 10^3$ s ($m$/eV), will eventually be obtained using neutrinos from distant astrophysical sources, but large uncertainties --- in neutrino properties, source properties, and detection aspects --- do not allow this yet. However, there is a way forward now. We show that IceCube diffuse neutrino measurements, supplemented by improvements expected in the near term, can increase sensitivity to $tau sim 10$ s ($m$/eV) for all neutrino mass eigenstates. We provide a roadmap for the necessary analyses and show how to manage the many uncertainties. If limits are set, this would definitively rule out the long-considered possibility that neutrino decay affects solar, atmospheric, or terrestrial neutrino experiments.