Her X-1, one of the brightest and best studied X-ray binaries, shows a cyclotron resonant scattering feature (CRSF) near 37 keV. This makes it an ideal target for detailed study with the Nuclear Spectroscopic Telescope Array (NuSTAR), taking advantage of its excellent hard X-ray spectral resolution. We observed Her X-1 three times, coordinated with Suzaku, during one of the high flux intervals of its 35d super-orbital period. This paper focuses on the shape and evolution of the hard X-ray spectrum. The broad-band spectra can be fitted with a powerlaw with a high-energy cutoff, an iron line, and a CRSF. We find that the CRSF has a very smooth and symmetric shape, in all observations and at all pulse-phases. We compare the residuals of a line with a Gaussian optical depth profile to a Lorentzian optical depth profile and find no significant differences, strongly constraining the very smooth shape of the line. Even though the line energy changes dramatically with pulse phase, we find that its smooth shape does not. Additionally, our data show that the continuum is only changing marginally between the three observations. These changes can be explained with varying amounts of Thomson scattering in the hot corona of the accretion disk. The average, luminosity-corrected CRSF energy is lower than in past observations and follows a secular decline. The excellent data quality of NuSTAR provides the best constraint on the CRSF energy to date.