[Abridged] We use the Planck all-sky submm and mm maps to search for rare sources distinguished by extreme brightness, a few hundreds of mJy, 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 and 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 (CIB). We perform a dedicated Herschel-SPIRE follow-up of 234 such Planck targets, finding a significant excess of red 350 and 500um 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 350um. About 3% are candidate lensed systems, all 12 of which have secure spectroscopic confirmations, placing them at redshifts z>2.2. The galaxy overdensities are detected with high significance, half of the sample showing statistical significance above 10sigma. The SPIRE photometric redshifts of galaxies in overdensities suggest a peak at z~2. Under the Td=35K assumption, we derive an infrared (IR) luminosity for each SPIRE source of about 4x10^12 Lsun, yielding star formation rates of typically 700 Msun.yr^-1. If the observed overdensities are actual gravitationally-bound structures, the total total star formation rates reaches 7x10^3 Msun.yr^-1. Taken together, these sources show the signatures of high-z (z>$) protoclusters of intensively star-forming galaxies. All these observations confirm the uniqueness of our sample and demonstrate the ability of the all-sky Planck-HFI cold sources to select populations of cosmological and astrophysical interest for structure formation studies.