Velocity dispersions sigma and Mg absorption line strengths Mg-b have been measured for a sample of 16 ellipticals in three clusters at a redshift of 0.37. Like local cluster ellipticals, these objects show a correlation between Mg-b and sigma. However, at any given sigma, the mean Mg-b of the ellipticals at z = 0.37 is weaker than the mean Mg-b of their local relatives in the Coma and Virgo clusters. The Mg-b weakening is smallest for the most luminous ellipticals and larger for the fainter objects. This is unambiguous evidence for small but significant passive evolution of the stellar populations of elliptical galaxies with redshift. It requires that the bulk of the stars in cluster ellipticals has formed at z > 2. The most luminous objects may even have formed at z > 4. The Mg-b-sigma test is a very reliable estimator for the evolution of old stellar populations because it is virtually independent from the stellar initial mass function (IMF) and from the metallicities of the galaxies. Furthermore, the influence of selection effects is minimal. Consistent with the weakening of Mg-b we find evidence for a B-band luminosity evolution of about 0.5 +/- 0.1 mag at z = 0.37 from the Faber-Jackson relation. The combined information about the evolution of Mg-b and luminosity allows us to constrain both the slope of the IMF in ellipticals and the cosmological deceleration parameter q(0). Our present measurements are compatible with a standard Salpeter IMF and a q(0) of 0.5 +/- 0.5.