High-energy astrophysical neutrinos are a novel arena to test for the presence of new neutrino physics. With them, we can look for new physics at scales of tens of TeV to a few PeV, far beyond the reach of laboratory experiments. Even tiny modifications from new physics might accumulate over the presumed cosmological-scale baselines and become detectable. New physics models include, for instance, enhanced neutrino-neutrino interactions, violation of fundamental symmetries, active-sterile neutrino mixing, and neutrino decay. For the latter, we use current flavor composition results from IceCube to improve the limits on neutrino lifetimes. To tap into the full potential of flavor composition measurements, we propose a technique to distinguish between particle showers initiated by electron-neutrinos and tau-neutrinos on a statistical basis. Together with higher statistics and detector upgrades, it will bolster the prospects of finding new physics and of identifying the neutrino sources.