ABSTRACT ALMA observations have revealed the presence of dust in the first generations of galaxies in the Universe. However, the dust temperature Td remains mostly unconstrained due to the few available FIR continuum data at redshift $z$ > 5. This introduces large uncertainties in several properties of high-$z$ galaxies, namely their dust masses, infrared luminosities, and obscured fraction of star formation. Using a new method based on simultaneous C $\scriptstyle \rm II$ 158-μm line and underlying dust continuum measurements, we derive Td in the continuum and C $\scriptstyle \rm II$ detected $z$ ≈ 7 galaxies in the ALMA Large Project REBELS sample. We find 39 < Td < 58 K, and dust masses in the narrow range Md = (0.9−3.6) × 107 M⊙. These results allow us to extend for the first time the reported Td($z$) relation into the Epoch of Reionization. We produce a new physical model that explains the increasing Td($z$) trend with the decrease of gas depletion time, tdep = Mg/SFR, induced by the higher cosmological accretion rate at early times; this hypothesis yields Td ∝ (1 + $z$)0.4. The model also explains the observed Td scatter at a fixed redshift. We find that dust is warmer in obscured sources, as a larger obscuration results in more efficient dust heating. For UV-transparent (obscured) galaxies, Td only depends on the gas column density (metallicity), $T_{\rm d} \propto N_{\rm H}^{1/6}$ (Td ∝ Z−1/6). REBELS galaxies are on average relatively transparent, with effective gas column densities around NH ≃ (0.03−1) × 1021 cm−2. We predict that other high-$z$ galaxies (e.g. MACS0416-Y1, A2744-YD4), with estimated Td ≫ 60 K, are significantly obscured, low-metallicity systems. In fact, Td is higher in metal-poor systems due to their smaller dust content, which for fixed LIR results in warmer temperatures.