The Planck mission, thanks to its large frequency range and all-sky coverage, has a unique potential for systematically detecting the brightest, and rarest, submillimetre sources on the sky, including distant objects in the high-redshift Universe traced by their dust emission. A novel method, based on a component-separation procedure using a combination of Planck and IRAS data, has been applied to select the most luminous cold submm sources with spectral energy distributions peaking between 353 and 857GHz at 5 resolution. A total of 2151 Planck high-z source candidates (the PHZ) have been detected in the cleanest 26% of the sky, with flux density at 545GHz above 500mJy. Embedded in the cosmic infrared background close to the confusion limit, these high-z candidates exhibit colder colours than their surroundings, consistent with redshifts z>2, assuming a dust temperature of 35K and a spectral index of 1.5. First follow-up observations obtained from optical to submm have confirmed that this list consists of two distinct populations. A small fraction (around 3%) of the sources have been identified as strongly gravitationally lensed star-forming galaxies, which are amongst the brightest submm lensed objects (with flux density at 545GHz ranging from 350mJy up to 1Jy) at redshift 2 to 4. However, the vast majority of the PHZ sources appear as overdensities of dusty star-forming galaxies, having colours consistent with z>2, and may be considered as proto-cluster candidates. The PHZ provides an original sample, complementary to the Planck Sunyaev-Zeldovich Catalogue; by extending the population of the virialized massive galaxy clusters to a population of sources at z>1.5, the PHZ may contain the progenitors of todays clusters. Hence the PHZ opens a new window on the study of the early ages of structure formation, and the understanding of the intensively star-forming phase at high-z.