A new fixed-target experiment at the CERN SPS accelerator is proposed that will use decays of charm mesons to search for Heavy Neutral Leptons (HNLs), which are right-handed partners of the Standard Model neutrinos. The existence of such particles is strongly motivated by theory, as they can simultaneously explain the baryon asymmetry of the Universe, account for the pattern of neutrino masses and oscillations and provide a Dark Matter candidate. Cosmological constraints on the properties of HNLs now indicate that the majority of the interesting parameter space for such particles was beyond the reach of the previous searches at the PS191, BEBC, CHARM, CCFR and NuTeV experiments. For HNLs with mass below 2 GeV, the proposed experiment will improve on the sensitivity of previous searches by four orders of magnitude and will cover a major fraction of the parameter space favoured by theoretical models. The discovery of a HNL would have a great impact on our understanding of nature and open a new area for future research.