The observation of high-energy astrophysical neutrinos by the IceCube Neutrino Observatory has opened up a new window to the universe. These neutrinos traverse the longest distances from their sources and have the largest energy ever observed. These neutrinos open a new trail to search for new physics that covers parameter space not accessible to terrestrial neutrino experiments. In this Colloquia, I will explain the inner workings of the IceCube neutrino observatory, discuss the latest measurements of high-energy astrophysical neutrinos, and provide examples of new physics searches with these neutrinos.