Abstract We select and characterize a sample of massive (log(M _*/M _⊙) > 10.6) quiescent galaxies (QGs) at 3 < z < 5 in the latest Cosmological Evolution Survey catalog (COSMOS2020). QGs are selected using a new rest-frame color-selection method, based on their probability of belonging to the quiescent group defined by a Gaussian mixture model (GMM) trained on rest-frame colors (NUV − U, U − V, V − J) of similarly massive galaxies at 2 < z < 3. We calculate the quiescent probability threshold above which a galaxy is classified as quiescent using simulated galaxies from the shark semi-analytical model. We find that, at z ≥ 3 in shark, the GMM/NUVU − VJ method outperforms classical rest-frame UVJ selection and is a viable alternative. We select galaxies as quiescent based on their probability in COSMOS2020 at 3 < z < 5, and compare the selected sample to both UVJ- and NUVrJ-selected samples. We find that, although the new selection matches UVJ and NUVrJ in number, the overlap between color selections is only ∼50%–80%, implying that rest-frame color commonly used at lower-redshift selections cannot be equivalently used at z > 3. We compute median rest-frame spectral energy distributions for our sample and find the median QG at 3 < z < 5 has a strong Balmer/4000 Å break, and residual NUV flux indicating recent quenching. We find the number densities of the entire quiescent population (including post-starbursts) more than doubles from 3.5 ± 2.2 × 10⁻⁶ Mpc⁻³ at 4 < z < 5 to 1.4 ± 0.4 × 10⁻⁵ Mpc⁻³ at 3 < z < 4, confirming that the onset of massive galaxy quenching occurs as early as 3 < z < 5.