We report the identification of an extreme protocluster of galaxies in the early universe whose core (nicknamed Distant Red Core, DRC, because of its very red color in Herschel SPIRE bands) is formed by at least 10 dusty star-forming galaxies (DSFGs), spectroscopically confirmed to lie at z(spec) = 4.002 via detection of [C I](1-0), (CO)-C-12(6-5), (CO)-C-12(4-3), (CO)-C-12(2-1), and H2O(2(11)-2(02)) emission lines with ALMA and ATCA. These DSFGs are distributed over a 260 kpc x 310 kpc region and have a collective obscured star formation rate (SFR) of similar to 6500 M-circle dot yr(-1), considerably higher than those seen before in any protocluster at z greater than or similar to 4. Most of the star formation is taking place in luminous DSFGs since no Ly alpha emitters are detected in the protocluster core, apart from a Ly alpha blob located next to one of the DRC components, extending over 60 kpc. The total obscured SFR of the protocluster could rise to SFR similar to 14,400 M-circle dot yr(-1) if all the members of an overdensity of bright DSFGs discovered around DRC in a wide-field Large APEX BOlometer CAmera 870 mu m image are part of the same structure. [C I](1-0) emission reveals that DRC has a total molecular gas mass of at least M-H2 similar to 6.6 x 10(11) M-circle dot, and its total halo mass could be as high as similar to 4.4 x 10(13) M-circle dot, indicating that it is the likely progenitor of a cluster at least as massive as Coma at z = 0.