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 (CFHT). 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 characterise the faintest Milky Way satellites, and to map the (metal-poor) substructure in the Galactic halo. The current Pristine footprint comprises over 1,000 deg2 in the Galactic halo ranging from b~30 to 78 and covers many known stellar substructures. We demonstrate that, for SDSS stellar objects, we can calibrate the photometry at the 0.02-magnitude level. The comparison with existing spectroscopic metallicities from SDSS/SEGUE and LAMOST 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 ~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% and 85% 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.