The most metal-poor stars in the Galaxy are relics from the first generations of star formation, and their properties can reveal key information about the formation and evolution of the Milky Way. However, only a small number of these extremely rare stars are currently known, due to the difficulty in finding them amongst the overwhelmingly more abundant stars of higher metallicity. In this talk, I will present the Pristine survey, a narrow-band photometric survey in the wavelength region around the Ca H&K absorption lines designed to efficiently search for extremely metal-poor (EMP) stars. In the first three years of the survey, we have covered ~2,500 square degrees of sky in the Northern hemisphere using the CFHT on Mauna Kea in Hawaii, as well as a sizeable spectroscopic follow-up sample using mostly the INT and WHT in La Palma. With this data, we have demonstrated success rates of 70% for finding stars with [Fe/H] < -2.5, and 22% for stars with [Fe/H] < -3.0. This represents a significant improvement upon previous searches for EMP stars, which have reported success rates of 3-4%. With this efficiency, the Pristine survey is poised to make a significant contribution to constraining the metal-poor tail of the metallicity distribution function, as well as increasing the number of known ultra metal-poor (UMP) stars in the literature. In addition, I will discuss how the Pristine survey is being used to characterise the faint dwarf galaxy population, and analyse substructure in the Galactic Halo.