We present near-infrared spectroscopic confirmations of a sample of 16 photometrically-selected galaxies with stellar masses log(M_star/M_sun) > 11 at redshift z > 3 from the XMM-VIDEO and COSMOS-UltraVISTA fields using Keck/MOSFIRE as part of the MAGAZ3NE survey. Eight of the ultra-massive galaxies (UMGs) have specific star formation rates (sSFR) < 0.03 Gyr-1, with negligible emission lines. Another seven UMGs show emission lines consistent with active galactic nuclei and/or star formation, while only one UMG has sSFR > 1 Gyr-1. Model star formation histories of these galaxies describe systems that formed the majority of their stars in vigorous bursts of several hundred Myr duration around 4 < z < 6during which hundreds to thousands of solar masses were formed per year. These formation ages of < 1 Gyr prior to observation are consistent with ages derived from measurements of Dn(4000) and EW0(Hdelta). Rapid quenching followed these bursty star-forming periods, generally occurring less than 350 Myr before observation, resulting in post-starburst SEDs and spectra for half the sample. The rapid formation timescales are consistent with the extreme star formation rates observed in 4 < z < 7 dusty starbursts observed with ALMA, suggesting that such dusty galaxies are progenitors of these UMGs. While such formation histories have been suggested in previous studies, the large sample introduced here presents the most compelling evidence yet that vigorous star formation followed by rapid quenching is almost certainly the norm for high mass galaxies in the early universe. The UMGs presented here were selected to be brighter than Ks = 21.7 raising the intriguing possibility that even (fainter) older quiescent UMGs could exist at this epoch.