We have used the Planck all-sky submillimetre and millimetre maps to search for rare sources distinguished by extreme brightness, a few hundred millijanskies, and their potential for being situated at high redshift. These "cold" Planck sources, selected using the High Frequency Instrument (HFI) directly from the maps and from the Planck Catalogue of Compact Sources (PCCS), all satisfy the criterion of having their rest-frame far-infrared peak redshifted to the frequency range 353-857 GHz. This colour-selection favours galaxies in the redshift range z = 2-4, which we consider as cold peaks in the cosmic infrared background. With a 4.'5 beam at the four highest frequencies, our sample is expected to include overdensities of galaxies in groups or clusters, lensed galaxies, and chance line-of-sight projections. We perform a dedicated Herschel-SPIRE follow-up of 234 such Planck targets, finding a significant excess of red 350 and 500 mu m sources, in comparison to reference SPIRE fields. About 94% of the SPIRE sources in the Planck fields are consistent with being overdensities of galaxies peaking at 350 mu m, with 3% peaking at 500 mu m, and none peaking at 250 mu m. About 3% are candidate lensed systems, all 12 of which have secure spectroscopic confirmations, placing them at redshifts z > 2.2. Only four targets are Galactic cirrus, yielding a success rate in our search strategy for identifying extragalactic sources within the Planck beam of better than 98%. The galaxy overdensities are detected with high significance, half of the sample showing statistical significance above 10 sigma. The SPIRE photometric redshifts of galaxies in overdensities suggest a peak at z similar or equal to 2, assuming a single common dust temperature for the sources of T-d = 35 K. Under this assumption, we derive an infrared (IR) luminosity for each SPIRE source of about 4x10(12) L-circle dot, yielding star formation rates of typically 700 M-circle dot yr(-1). If the observed overdensities are actual gravitationally-bound structures, the total IR luminosity of all their SPIRE-detected sources peaks at 4 x 10(13) L-circle dot, leading to total star formation rates of perhaps 7 x 10(3) M-circle dot yr(-1) per overdensity. Taken together, these sources show the signatures of high-z (z > 2) protoclusters of intensively star-forming galaxies. All these observations confirm the uniqueness of our sample compared to reference samples and demonstrate the ability of the all-sky Planck-HFI cold sources to select populations of cosmological and astrophysical interest for structure formation studies.