We present spatially resolved stellar rotation velocity and velocity dispersion profiles form Keck/LRIS absorption-line spectra for 25 galaxies, mostly visually classified ellipticals, in three clusters at z=0.5. We interpret the kinematical data and HST photometry using oblate axisymmetric two-integral f(E,Lz) dynamical models based on the Jeans equations. This yields good fits, provided that the seeing and observational characteristics are carefully modeled. The fits yield for each galaxy the dynamical M/L and a measure of the galaxy rotation rate. Paper II addresses the implied M/L evolution. Here we study the rotation-rate evolution by comparison to a sample of local elliptical galaxies of similar present-day luminosity. The brightest galaxies in the sample all rotate too slowly to account for their flattening, as is also observed at z=0. But the average rotation rate is higher at z=0.5 than locally. This may be due to a higher fraction of misclassified S0 galaxies (although this effect is insufficient to explain the observed strong evolution of the cluster S0 fraction with redshift). Alternatively, dry mergers between early-type galaxies may have decreased the average rotation rate over time. It is unclear whether such mergers are numerous enough in clusters to explain the observed trend quantitatively. Disk-disk mergers may affect the comparison through the so-called progenitor bias, but this cannot explain the direction of the observed rotation-rate evolution. Additional samples are needed to constrain possible environmental dependencies and cosmic variance in galaxy rotation rates. Either way, studies of the internal stellar dynamics of distant galaxies provide a valuable new approach for exploring galaxy evolution.