We exploit the continuity equation approach and the `main sequence star-formation timescales to show that the observed high abundance of galaxies with stellar masses > a few 10^10 M_sun at redshift z>4 implies the existence of a galaxy population featuring large star formation rates (SFRs) > 10^2 M_sun/yr in heavily dust-obscured conditions. These galaxies constitute the high-redshift counterparts of the dusty star-forming population already surveyed for z<3 in the far-IR band by the Herschel space observatory. We work out specific predictions for the evolution of the corresponding stellar mass and SFR functions out to z~10, elucidating that the number density at z<8 for SFRs >30 M_sun/yr cannot be estimated relying on the UV luminosity function alone, even when standard corrections for dust extinction based on the UV slope are applied. We compute the number counts and redshift distributions (including galaxy-scale gravitational lensing) of this galaxy population, and show that current data from AzTEC-LABOCA, SCUBA-2 and ALMA-SPT surveys are already digging into it. We substantiate how an observational strategy based on a color preselection in the far-IR or (sub-)mm band with Herschel and SCUBA-2, supplemented by photometric data via on-source observations with ALMA, can allow to reconstruct the bright end of the SFR functions out to z~8. In parallel, such a challenging task can be managed by exploiting current UV surveys in combination with (sub-)mm observations by ALMA and NIKA2 and/or radio observations by SKA and its precursors.