Abstract We present the census of massive (log(M */M ⊙) > 11) galaxies at 3 < z < 6 identified over the COSMOS/UltraVISTA Ultra-Deep field stripes: consisting of ≈100 and ≈20 high-confidence candidates at 3 < z < 4 and 4 < z < 6, respectively. The 3 < z < 4 population is comprised of post-starburst, UV-star-forming, and dusty star-forming galaxies in roughly equal fractions, while UV-star-forming galaxies dominate at 4 < z < 6 . We account for various sources of biases in the spectral energy distribution (SED) modeling, finding that the treatment of emission line contamination is essential for understanding the number densities and mass growth histories of massive galaxies at z > 3. The significant increase in observed number densities at z ∼ 4 (> × 5 in ≲600 Myr) implies that this is the epoch at which log(M */M ⊙) > 11 galaxies emerge in significant numbers, with stellar ages (≈500–900 Myr) indicating rapid formation epochs as early as z ∼ 7. Leveraging ancillary multiwavelength data sets, we perform panchromatic SED modeling to constrain the total star formation activity of the sample. The star formation activity of the sample is generally consistent with being on the star formation main sequence at the considered redshifts, with ≈15%–25% of the population showing evidence of suppressed star formation rates, indicating that quenching mechanisms are already at play by z ∼ 4. We stack the available Hubble Space Telescope imaging, confirming their compact nature (r e ≲ 2.2 kpc), consistent with expected sizes of high-z star-forming galaxies. Finally, we discuss how our results are in-line with the early formation epochs and short formation timescales inferred from the fossil records of the most massive galaxies in the universe.