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 μ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 μm, with 3% peaking at 500 μm, and none peaking at 250 μ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σ. The SPIRE photometric redshifts of galaxies in overdensities suggest a peak at z ≃ 2, assuming a single common dust temperature for the sources of Td = 35 K. Under this assumption, we derive an infrared (IR) luminosity for each SPIRE source of about 4 × 1012 L⊙, yielding star formation rates of typically 700 M⊙ yr-1. If the observed overdensities are actual gravitationally-bound structures, the total IR luminosity of all their SPIRE-detected sources peaks at 4 × 1013 L⊙, leading to total star formation rates of perhaps 7 × 103 M⊙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.