The evolution of the temperature in the intergalactic medium is related to the reionization of hydrogen and helium , and has important consequences for our understanding of the Ly \alpha forest and of galaxy formation in gravitational models of large-scale structure . We measure the temperature-density relation of intergalactic gas from Ly \alpha forest observations of eight quasar spectra with high resolution and signal-to-noise ratio , using a new line fitting technique to obtain a lower cutoff of the distribution of line widths from which the temperature is derived . We carefully test the accuracy of this technique to recover the gas temperature with a hydrodynamic simulation . The temperature at redshift \bar { z } = ( 3.9 , 3.0 , 2.4 ) is best determined at densities slightly above the mean : T _ { \star } = ( 20200 \pm 2700 , 20200 \pm 1300 , 22600 \pm 1900 ) K ( statistical error bars ) for gas density ( in units of the mean density ) \Delta _ { \star } = ( 1.42 \pm 0.08 , 1.37 \pm 0.11 , 1.66 \pm 0.11 ) . The power-law index of the temperature-density relation , defined by T = T _ { \star } ( \Delta _ { g } / \Delta _ { \star } ) ^ { \gamma - 1 } , is \gamma - 1 = ( 0.43 \pm 0.45 , 0.29 \pm 0.30 , 0.52 \pm 0.14 ) for the same three redshifts . The temperature at the fixed over-density \Delta = 1.4 is T _ { 1.4 } = ( 20100 \pm 2800 , 20300 \pm 1400 , 20700 \pm 1900 ) K. These temperatures are higher than expected for photoionized gas in ionization equilibrium with a cosmic background , and can be explained by a gradual additional heating due to on-going He II reionization . The measurement of the temperature reduces one source of uncertainty in the lower limit to the baryon density implied by the observed mean flux decrement . We find that the temperature can not be reliably measured for under-dense gas , because the velocities due to expansion always dominate the widths of the corresponding weak lines .