Targeted mutagenesis in mice has shown that genes from a wide variety of gene families are involved in memory formation. The efficient identification of genes involved in learning and memory could be achieved by random mutagenesis combined with high-throughput phenotyping. Here, we provide the first report of a mutagenesis screen that has generated memory mutants in the mouse. We tested a group of N-ethyl-N-nitrosourea (ENU) mutagenized mice in the conditioned fear paradigm. We screened for both dominant and recessive mutations that caused impairments in contextual or tone fear conditioning. Heritability testing confirmed three fear conditioning mutants, i.e., Forgetful, Slowlearner, and Scatterbrain. All three have a learning or short-term memory deficit in contextual fear conditioning. Forgetful was further characterized and showed a highly specific phenotype. The contextual fear-conditioning deficit was apparent when Forgetful was trained with tone-shock pairings, but not when trained with shock alone. The deficit was not due to changes in shock sensitivity or anxiety. Forgetful was not impaired in two other memory tests (hidden platform version of Morris water maze and object recognition). Our data show that a mutagenesis screen can generate mutant mice with highly specific memory phenotypes that can supplement existing mice with targeted mutations. Mapping of Slowlearner found linkage to a region of chromosome 12 (LOD score of 6.5 close to D12Mit171), which suggests that ENU mutants should enable the positional cloning of genes involved in memory formation.