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 validated and characterized on numerous simulations, and applied to select the most luminous cold submillimetre sources with spectral energy distributions peaking between 353 and 857 GHz 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 545 GHz above 500 mJy. 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 Txgal = 35 K and a spectral index of βxgal = 1.5. Exhibiting extremely high luminosities, larger than 1014L⊙, the PHZ objects may be made of multiple galaxies or clumps at high redshift, as suggested by a first statistical analysis based on a comparison with number count models. Furthermore, first follow-up observations obtained from optical to submillimetre wavelengths, which can be found in companion papers, 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 at redshift 2 to 4, while the vast majority of the PHZ sources appear as overdensities of dusty star-forming galaxies, having colours consistent with being at z > 2, and may be considered as proto-cluster candidates. The PHZ provides an original sample, which is complementary to the Planck Sunyaev-Zeldovich Catalogue (PSZ2); by extending the population of virialized massive galaxy clusters detected below z < 1.5 through their SZ signal to a population of sources at z > 1.5, the PHZ may contain the progenitors of today's clusters. Hence the Planck list of high-redshift source candidates opens a new window on the study of the early stages of structure formation, particularly understanding the intensively star-forming phase at high-z. The catalogue is only available at the CDS via anonymous ftp to http://cdsarc.u-strasbg.fr (http://130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/596/A100