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.