We present the Pristine survey, a new narrow-band photometric survey focused on the metallicity-sensitive Ca H&K lines and conducted in the Northern hemisphere with the wide-field imager MegaCam on the Canada-France-Hawaii Telescope. This paper reviews our overall survey strategy and discusses the data processing and metallicity calibration. Additionally we review the application of these data to the main aims of the survey, which are to gather a large sample of the most metal-poor stars in the Galaxy, to further characterize the faintest Milky Way satellites, and to map the (metal-poor) substructure in the Galactic halo. The current Pristine footprint comprises over 1000 deg(2) in the Galactic halo ranging from b similar to 30 degrees to similar to 78 degrees and covers many known stellar substructures. We demonstrate that, for Sloan Digital Sky Survey (SDSS) stellar objects, we can calibrate the photometry at the 0.02-mag level. The comparison with existing spectroscopic metallicities from SDSS/Sloan Extension for Galactic Understanding and Exploration (SEGUE) and Large Sky Area Multi-Object Fiber Spectroscopic Telescope shows that, when combined with SDSS broad-band g and i photometry, we can use the CaHK photometry to infer photometric metallicities with an accuracy of similar to 0.2 dex from [Fe/H] = -0.5 down to the extremely metal-poor regime ([Fe/H] < -3.0). After the removal of various contaminants, we can efficiently select metal-poor stars and build a very complete sample with high purity. The success rate of uncovering [Fe/H](SEGUE) < -3.0 stars among [Fe/H](Pristine) < -3.0 selected stars is 24 per cent, and 85 per cent of the remaining candidates are still very metal poor ([Fe/H]<-2.0). We further demonstrate that Pristine is well suited to identify the very rare and pristine Galactic stars with [Fe/H] < -4.0, which can teach us valuable lessons about the early Universe.