We present spectra of the most massive quiescent galaxy yet discovered at $z>3$, spectroscopically confirmed via the detection of Balmer absorption features in the $H-$ and $K-$bands of Keck/MOSFIRE. The spectra confirm a galaxy with no significant ongoing star formation, consistent with the lack of rest-frame UV flux and overall photometric spectral energy distribution. With a stellar mass of $3.1^{+0.1}_{-0.2} \times 10^{11} ~\rm{M}_\odot$ at $z = 3.493$, this galaxy is nearly three times more massive than the highest redshift spectroscopically confirmed absorption-line identified galaxy known. The star-formation history of this quiescent galaxy implies that it formed $>1000 ~\rm{M}_\odot$/yr for almost 0.5 Gyr beginning at $z\sim7.2$, strongly suggestive that it is the descendant of massive dusty star-forming galaxies at $5<z<7$ recently observed with ALMA. While galaxies with similarly extreme stellar masses are reproduced in some simulations at early times, such a lack of ongoing star formation is not seen there. This suggests the need for a more rapid quenching process than is currently prescribed, challenging our current understanding of how ultra-massive galaxies form and evolve in the early Universe.