Our current knowledge of cosmic star-formation history during the first two billion years (corresponding to redshift z >3) is mainly based on galaxies identified in rest-frame ultraviolet light. However, this population of galaxies is known to under-represent the most massive galaxies, which have rich dust content and/or old stellar populations. This raises the questions of the true abundance of massive galaxies and the star-formation-rate density in the early universe. Although several massive galaxies that are invisible in the ultraviolet have recently been confirmed at early epochs, most of them are extreme starbursts with star-formation rates exceeding 1000 solar masses per year, suggesting that they are unlikely to represent the bulk population of massive galaxies. Here we report submillimeter (wavelength 870um) detections of 39 massive star-forming galaxies at z > 3, which are unseen in the spectral region from the deepest ultraviolet to the near-infrared. With a space density of about $2 \times 10^{-5}$ per cubic megaparsec (two orders of magnitudes higher than extreme starbursts) and star-formation rates of 200 solar masses per year, these galaxies represent the bulk population of massive galaxies that have been missed from previous surveys. They contribute a total star-formation-rate density ten times larger than that of equivalently massive ultraviolet-bright galaxies at z >3. Residing in the most massive dark matter halos at their redshifts, they are probably the progenitors of the largest present-day galaxies in massive groups and clusters. Such a high abundance of massive and dusty galaxies in the early universe challenges our understanding of massive-galaxy formation.