Parameterizing hypothetical violation of Lorentz invariance at high energies using the framework of effective quantum field theory, we discuss its effect on the formation of atmospheric showers by very-high-energy gamma rays. In the scenario where Lorentz invariance violation leads to a decrease of the photon velocity with energy the formation of the showers is suppressed compared to the Lorentz invariant case. Absence of such suppression in the high-energy part of spectrum of the Crab nebula measured independently by HEGRA and H.E.S.S. collaborations is used to set lower bounds on the energy scale of Lorentz invariance violation. These bounds are competitive with the strongest existing constraints obtained from timing of variable astrophysical sources and the absorption of TeV photons on the extragalactic background light. They will be further improved by the next generation of multi-TeV gamma-ray observatories.