We derive absorption line indices of elliptical galaxies in clusters at intermediate redshift (z approximate to 0.37) from medium-resolution spectroscopy together with kinematical parameters, These galaxies exhibit a relationship between the Line strength of Mg-b (lambda(0) approximate to 5170 Angstrom) and their internal velocity dispersion sigma, similar to local dynamically hot galaxies. For any given sigma, however, the Mg-b line strength of the distant ellipticals is significantly lower than the mean value of the nearby sample. The difference in Mg-b between the two samples is small ([Delta Mg-b] approximate to -0.4 Angstrom) and can be fully attributed to the lower age of the distant stellar populations in accordance with the passive evolution model for elliptical galaxies. The low reduction of Mg-b at a look-back time of about 5 Gyr requires that the bulk of the stars in cluster ellipticals have formed at very high redshifts of z(f) > 2. For the most massive galaxies, where the reduction is even lower, z(f) probably exceeds 4. Unlike most methods used to measure the evolution of elliptical galaxies using luminosities, surface brightnesses or colours, the Mg-b-sigma test does not depend on corrections for extinction and cosmic expansion (k-correction) and depends only slightly on the slope of the initial mass function (IMF). The combination of a kinematical parameter with a stellar population indicator allows us to study the evolution of very similar objects. In addition, the good mass estimate provided by sigma means that the selection criteria for the galaxy sample as a whole are wellcontrolled. In quantitative agreement with the reduction of the Mg-b absorption, we find an increase of the B magnitude of [Delta M-B] approximate to -0.5 mag at fixed a from the Faber-Jackson relation. The brightening of the ellipticals at z = 0.37 arises solely from the evolution of their stellar populations and is of the same order as the change in magnitudes observed when varying the deceleration parameter q(0) from -0.5 to +0.5 at this redshift. Studying the evolution of the Mg-b-sigma relation in combination with that of the Faber-Jackson relation allows us to constrain both the slope of the IMF and the value of the deceleration parameter. Our current data (including measurement errors) are compatible with the standard Salpeter IMF and q(0) = 0.5 +/- 0.5.