We prove that the fully discrete lattice Boltzmann method is invariant with respect to Galilean transformation. Based on this finding, a novel class of shifted lattices is proposed which dramatically increases the operating range of lattice Boltzmann simulations, in particular, for gas dynamics applications. A simulation of vortex-shock interaction is used to demonstrate the accuracy and efficiency of the proposed lattices. With one single algorithm it is now possible to simulate a broad range of applications, from low Mach number flows to transonic and supersonic flow regimes.