Along their long propagation from production to detection, neutrinos undergo flavour conversions that convert their types or flavours 1,2. High-energy astrophysical neutrinos propagate unperturbed over a billion light years in vacuum 3 and are sensitive to small effects caused by new physics. Effects of quantum gravity 4 are expected to appear at the Planck energy scale. Such a high-energy universe would have existed only immediately after the Big Bang and is inaccessible by human technologies. On the other hand, quantum gravity effects may exist in our low-energy vacuum 5–8, but are suppressed by inverse powers of the Planck energy. Measuring the coupling of particles to such small effects is difficult via kinematic observables, but could be observable through flavour conversions. Here we report a search with the IceCube Neutrino Observatory, using astrophysical neutrino flavours 9,10 to search for new space–time structure. We did not find any evidence of anomalous flavour conversion in the IceCube astrophysical neutrino flavour data. We apply the most stringent limits of any known technologies, down to 10 −42 GeV −2 with Bayes factor greater than 10 on the dimension-six operators that parameterize the space–time defects. We thus unambiguously reach the parameter space of quantum-gravity-motivated physics.