We report the spectroscopic discovery of a massive quiescent galaxy at $z_{\rm spec}=7.29\pm0.01$, just $\sim700\,$Myr after the Big Bang. RUBIES-UDS-QG-z7 was selected from public JWST/NIRCam and MIRI imaging from the PRIMER survey and observed with JWST/NIRSpec as part of RUBIES. The NIRSpec/PRISM spectrum reveals one of the strongest Balmer breaks observed thus far at $z>6$, no emission lines, but tentative Balmer and Ca absorption features, as well as a Lyman break. Simultaneous modeling of the NIRSpec/PRISM spectrum and NIRCam and MIRI photometry (spanning $0.9-18\,\mu$m) shows that the galaxy formed a stellar mass of log$(M_*/M_\odot)=10.23^{+0.04}_{-0.04}$ in a rapid $\sim 100-200\,$Myr burst of star formation at $z\sim8-9$, and ceased forming stars by $z\sim8$ resulting in $\log \rm{sSFR/yr}^{-1}<-10$. We measure a small physical size of $209_{-24}^{+33}\,{\rm pc}$, which implies a high stellar mass surface density within the effective radius of $\log(\Sigma_{*,\rm e}/{\rm M_\odot\,kpc}^{-2})=10.85_{-0.12}^{+0.11}$ comparable to the densities measured in quiescent galaxies at $z\sim2-5$. The 3D stellar mass density profile of RUBIES-UDS-QG-z7 is remarkably similar to the central densities of local massive ellipticals, suggesting that at least some of their cores may have already been in place at $z>7$. The discovery of RUBIES-UDS-QG-z7 has strong implications for galaxy formation models: the estimated number density of quiescent galaxies at $z\sim7$ is $>100\times$ larger than predicted from any model to date, indicating that quiescent galaxies have formed earlier than previously expected.