We present the results of ten years of repeated measurements of the Cyclotron Resonance Scattering Feature (CRSF) in the spectrum of the binary X-ray pulsar Her X-1 and report the discovery of a positive correlation of the centroid energy of this absorption feature in pulse phase averaged spectra with source luminosity.Our results are based on a uniform analysis of observations bythe RXTE satellite from 1996 to 2005, using sufficiently long observations of 12 individual 35-day Main-On states of the source. The mean centroid energy E_c of the CRSF in pulse phase averaged spectra of Her X-1 during this time is around 40 keV, with significant variations from one Main-On state to the next. We find that the centroid energy of the CRSF in Her X-1 changes by ~5% in energy for a factor of 2 in luminosity. The correlation is positive, contrary to what is observed in some high luminosity transient pulsars. Our finding is the first significant measurement of a positive correlation between E_c and luminosity in any X-ray pulsar. We suggest that this behaviour is expected in the case of sub-Eddington accretion and present a calculation of a quantitative estimate, which is very consistent with the effect observed in Her X-1.We urge that Her X-1 is regularly monitored further and that other X-ray pulsars are investigated for a similar behaviour.