We introduce the ALMA Redshift 4 Survey (AR4S), a systematic ALMA survey of all the known galaxies with stellar mass (M*) larger than 5e10 Msun at 3.5<z<5 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 890um (180um 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+/-2 K for the whole sample, and extrapolate the Lir 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*, with a median sSFR=2.8+/-0.8 Gyr and a dispersion around that relation of 0.28+/-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.