ALMA observations have revealed the presence of dust in the first generations of galaxies in the Universe. However, the dust temperature $T_d$ 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 CII 158$\mu$m line and underlying dust continuum measurements, we derive $T_ d$ in the continuum and CII detected $z\approx 7$ galaxies in the ALMA Large Project REBELS sample. We find $39\ \mathrm{K} < T_d < 58\ \mathrm{K}$, and dust masses in the narrow range $M_d = (0.9-3.6)\times 10^7 M_{\odot}$. These results allow us to extend for the first time the reported $T_d(z)$ relation into the Epoch of Reionization. We produce a new physical model that explains the increasing $T_ d(z)$ trend with the decrease of gas depletion time, $t_{dep}=M_g/\mathrm{SFR}$, induced by the higher cosmological accretion rate at early times; this hypothesis yields $T_d \propto (1+z)^{0.4}$. The model also explains the observed $T_d$ 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, $T_d$ only depends on the gas column density (metallicity), $T_d \propto N_H^{1/6}$ ($T_d \propto Z^{-1/6}$). REBELS galaxies are on average relatively transparent, with effective gas column densities around $N_H \simeq (0.03-1)\times 10^{21} \mathrm{cm}^{-2}$. We predict that other high-$z$ galaxies (e.g. MACS0416-Y1, A2744-YD4), with estimated $T_d \gg 60$ K, are significantly obscured, low-metallicity systems. In fact $T_d$ is higher in metal-poor systems due to their smaller dust content, which for fixed $L_{ IR}$ results in warmer temperatures.