High-energy astrophysical neutrinos, recently discovered by IceCube, are fertile ground to look for new physics. Due to the high neutrino energies — tens of TeV to a few PeV — we can look for new physics at unexplored energies. Due to their cosmological-scale baselines — Mpc to Gpc — tiny new-physics effects, otherwise unobservable, could accumulate and become detectable. Possibilities include neutrino decay, violation of fundamental symmetries, and novel neutrino-neutrino interactions. I will show that the spectral features, angular distribution, and flavor composition of neutrinos could reveal the presence of new physics and, to an extent, its type. I will pay special attention to neutrino decay and show that IceCube can, with present-day data, already improve limits on neutrino lifetime by several orders of magnitude. In the future, more statistics, advances in detection techniques, and detector upgrades will enhance the sensitivity.