It is shown that the results of the Super-Kamiokande atmospheric neutrino experiment, interpreted in terms of nu(mu)<-->nu(tau) flavor transitions, can probe possible decoherence effects induced by new physics (e.g., by quantum gravity) with high sensitivity, supplementing current laboratory tests based on kaon oscillations and on neutron interferometry. By varying the (unknown) energy dependence of such effects, one can either obtain strong limits on their amplitude or use them to find an unconventional solution to the atmospheric nu anomaly based solely on decoherence.