Abstract: The observation by the IceCube Collaboration of a high-energy (E greater than or similar to 200 TeV) neutrino from the direction of the blazar TXS 0506+056 and the coincident observations of enhanced gamma-ray emissions from the same object by MAGIC and other experiments can be used to set stringent constraints on Lorentz violation in the propagation of neutrinos that is linear in the neutrino energy: Delta v = -E/M-1, where Delta v is the deviation from the velocity of light, and M-1 is an unknown high energy scale to be constrained by experiment. Allowing for a difference in neutrino and photon propagation times of similar to 10 days, we find that M-1 greater than or similar to 3 x 10(16) GeV. This improves on previous limits on linear Lorentz violation in neutrino propagation by many orders of magnitude, and the same is true for quadratic Lorentz violation.