Three billion years after the big bang (at redshift z = 2), half of the most massive galaxies were already old, quiescent systems with little to no residual star formation and extremely compact with stellar mass densities at least an order of magnitude larger than in low-redshift ellipticals, their descendants. Little is known about how they formed, but their evolved, dense stellar populations suggest formation within intense, compact starbursts 1-2 Gyr earlier (at 3 < z < 6). Simulations show that gas-rich major mergers can give rise to such starbursts, which produce dense remnants. Submillimeter-selected galaxies (SMGs) are prime examples of intense, gas-rich starbursts. With a new, representative spectroscopic sample of compact, quiescent galaxies at z = 2 and a statistically well-understood sample of SMGs, we show that z = 3-6 SMGs are consistent with being the progenitors of z = 2 quiescent galaxies, matching their formation redshifts and their distributions of sizes, stellar masses, and internal velocities. Assuming an evolutionary connection, their space densities also match if the mean duty cycle of SMG starbursts is 42(-29)(+40) Myr (consistent with independent estimates), which indicates that the bulk of stars in these massive galaxies were formed in a major, early surge of star formation. These results suggest a coherent picture of the formation history of the most massive galaxies in the universe, from their initial burst of violent star formation through their appearance as high stellar-density galaxy cores and to their ultimate fate as giant ellipticals.