We report Atacama Large Millimeter Array (ALMA) observations of four high-redshift dusty star-forming galaxy candidates selected from far-infrared (FIR)/submillimeter observations in the COSMOS field. We securely detect all galaxies in the continuum and spectroscopically confirm them at z = 3.62–5.85 using ALMA 3 mm line scans, detecting multiple CO and/or [C i] transitions. This includes the most distant dusty galaxy currently known in the COSMOS field, ID85001929 at z = 5.847. These redshifts are lower than we had expected, as these galaxies have substantially colder dust temperatures (i.e., their spectral energy distributions peak at longer rest-frame wavelengths) than most literature sources at z > 4. The observed cold dust temperatures are best understood as evidence for optically thick dust continuum in the FIR, rather than the result of low star formation efficiency with rapid metal enrichment. We provide direct evidence that, given their cold spectral energy distributions, cosmic microwave background (CMB) plays a significant role in biasing their observed Rayleigh–Jeans (RJ) slopes to unlikely steep values and, possibly, reducing their CO fluxes by a factor of two. We recover standard RJ slopes when the CMB contribution is taken into account. High-resolution ALMA imaging shows compact morphology and evidence for mergers. This work reveals a population of cold dusty star-forming galaxies that were underrepresented in current surveys and are even colder than typical main-sequence galaxies at the same redshift. High FIR dust optical depth might be a widespread feature of compact starbursts at any redshift.