We introduce the ALMA Redshift 4 Survey ( AR4S ) , a systematic ALMA survey of all the known galaxies with stellar mass ( M _ { \ast } ) larger than 5 \times 10 ^ { 10 } { M } _ { \odot } at 3.5 < z < 4.7 in the GOODS– south , UDS and COSMOS CANDELS fields . The sample we have analyzed in this paper is composed of 96 galaxies observed with ALMA at 890 \mu { m } ( 180 \mu { m } rest-frame ) with an on-source integration time of 1.3 { min } per galaxy . We detected 32 \% of the sample at more than 3 \sigma significance . Using the stacked ALMA and Herschel photometry , we derived an average dust temperature of 40 \pm 2 { K } for the whole sample , and extrapolate the L _ { IR } and { SFR } for all our galaxies based on their ALMA flux . We then used a forward modeling approach to estimate their intrinsic { sSFR } distribution , deconvolved of measurement errors and selection effects : we find a linear relation between { SFR } and M _ { \ast } , with a median { sSFR } = 2.8 \pm 0.8 { Gyr } and a dispersion around that relation of 0.28 \pm 0.13 { dex } . This latter value is consistent with that measured at lower redshifts , which is proof that the main sequence of star-forming galaxies was already in place at z = 4 , at least among massive galaxies . These new constraints on the properties of the main sequence are in good agreement with the latest predictions from numerical simulations , and suggest that the bulk of star formation in galaxies is driven by the same mechanism from z = 4 to the present day , that is , over at least 90 \% of the cosmic history . We also discuss the consequences of our results on the population of early quiescent galaxies . This paper is part of a series that will employ these new ALMA observations to explore the star formation and dust properties of the massive end of the z = 4 galaxy population .