We study the evolution of the dust temperature of galaxies in the SFR- M∗ plane up to z ~ 2 using far-infrared and submillimetre observations from the Herschel Space Observatory taken as part of the PACS Evolutionary Probe (PEP) and Herschel Multi-tiered Extragalactic Survey (HerMES) guaranteed time key programmes. Starting from a sample of galaxies with reliable star-formation rates (SFRs), stellar masses (M∗) and redshift estimates, we grid the SFR- M∗parameter space in several redshift ranges and estimate the mean dust temperature (Tdust) of each SFR-M∗ - z bin. Dust temperatures are inferred using the stacked far-infrared flux densities (100-500 μm) of our SFR-M∗ - z bins. At all redshifts, the dust temperature of galaxies smoothly increases with rest-frame infrared luminosities (LIR), specific SFRs (SSFR; i.e., SFR/M∗), and distances with respect to the main sequence (MS) of the SFR- M∗ plane (i.e., Δlog (SSFR)MS = log [SSFR(galaxy)/SSFRMS(M∗,z)]). The Tdust - SSFR and Tdust - Δlog (SSFR)MS correlations are statistically much more significant than the Tdust - LIR one. While the slopes of these three correlations are redshift-independent, their normalisations evolve smoothly from z = 0 and z ~ 2. We convert these results into a recipe to derive Tdust from SFR, M∗ and z, valid out to z ~ 2 and for the stellar mass and SFR range covered by our stacking analysis. The existence of a strong Tdust - Δlog (SSFR)MS correlation provides us with several pieces of information on the dust and gas content of galaxies. Firstly, the slope of the Tdust - Δlog (SSFR)MS correlation can be explained by the increase in the star-formation efficiency (SFE; SFR/Mgas) with Δlog (SSFR)MS as found locally by molecular gas studies. Secondly, at fixed Δlog (SSFR)MS, the constant dust temperature observed in galaxies probing wide ranges in SFR and M∗ can be explained by an increase or decrease in the number of star-forming regions with comparable SFE enclosed in them. And thirdly, at high redshift, the normalisation towards hotter dust temperature of the Tdust - Δlog (SSFR)MS correlation can be explained by the decrease in the metallicities of galaxies or by the increase in the SFE of MS galaxies. All these results support the hypothesis that the conditions prevailing in the star-forming regions of MS and far-above-MS galaxies are different. MS galaxies have star-forming regions with low SFEs and thus cold dust, while galaxies situated far above the MS seem to be in a starbursting phase characterised by star-forming regions with high SFEs and thus hot dust. Herschel is an ESA space observatory with science instruments provided by European-led Principal Investigator consortia and with important participation from NASA.Appendices are available in electronic form at http://www.aanda.org