We present spectroscopic observations for a sample of 36 Herschel-SPIRE 250-500um selected galaxies (HSGs) at 2<z<5 from the Herschel Multi-tiered Extragalactic Survey (HerMES). Redshifts are confirmed as part of a large redshift survey of Herschel-SPIRE-selected sources covering ~0.93deg^2 in six extragalactic legacy fields. Observations were taken with the Keck I Low Resolution Imaging Spectrometer (LRIS) and the Keck II DEep Imaging Multi-Object Spectrograph (DEIMOS). Precise astrometry, needed for spectroscopic follow-up, is determined by identification of counterparts at 24um or 1.4GHz using a cross-identification likelihood matching method. Individual source luminosities range from log(L_IR/Lsun)=12.5-13.6 (corresponding to star formation rates 500-9000Msun/yr, assuming a Salpeter IMF), constituting some of the most intrinsically luminous, distant infrared galaxies yet discovered. We present both individual and composite rest-frame ultraviolet spectra and infrared spectral energy distributions (SEDs). The selection of these HSGs is reproducible and well characterized across large areas of sky in contrast to most z>2 HyLIRGs in the literature which are detected serendipitously or via tailored surveys searching only for high-z HyLIRGs; therefore, we can place lower limits on the contribution of HSGs to the cosmic star formation rate density at (7+-2)x10^(-3)Msun/yr h^3Mpc^(-3) at z~2.5, which is >10% of the estimated total star formation rate density (SFRD) of the Universe from optical surveys. The contribution at z~4 has a lower limit of 3x10^(-3)Msun/yr h^3 Mpc^(-3), ~>20% of the estimated total SFRD. This highlights the importance of extremely infrared-luminous galaxies with high star formation rates to the build-up of stellar mass, even at the earliest epochs.