We report two secure ($z=3.775, 4.012$) and one tentative ($zapprox3.767$) spectroscopic confirmations of massive and quiescent galaxies through $K$-band observations with Keck/MOSFIRE and VLT/X-Shooter. The stellar continuum emission, the absence of strong nebular emission lines and the lack of significant far-infrared detections confirm the passive nature of these objects, disfavoring the alternative solution of low-redshift dusty star-forming interlopers. We derive stellar masses of $mathrm{log}(M_{star}/M_odot)sim11$ and ongoing star formation rates placing these galaxies $gtrsim 1-2$ dex below the main sequence at their redshifts. The adopted parametrization of the star formation history suggests that these sources experienced a strong ($langle rm SFR rangle sim 1200-3500,M_odot,mathrm{yr}^{-1}$) and short ($sim 50$ Myr) burst of star formation, peaking $sim 150-500$ Myr before the time of observation, all properties reminiscent of the characteristics of sub-millimeter galaxies (SMGs) at $z>4$. We investigate this connection by comparing the comoving number densities and the properties of these two populations. We find a fair agreement only with the deepest sub-mm surveys detecting not only the most extreme starbursts, but also more normal galaxies. We support these findings by further exploring the Illustris-TNG cosmological simulation, retrieving populations of both fully quenched massive galaxies at $zsim3-4$ and SMGs at $zsim4-5$, with number densities and properties in agreement with the observations at $zsim3$, but in increasing tension at higher redshift. Nevertheless, as suggested by the observations, not all the progenitors of quiescent galaxies at these redshifts shine as bright SMGs in their past and, similarly, not all bright SMGs quench by $zsim3$, both fractions depending on the threshold assumed to define the SMGs themselves.