Alzheimer's disease is a leading cause of morbidity and mortality with no cure and only limited treatment available. Obesity and type 2 diabetes are positively associated with the development of premature cognitive decline and Alzheimer's disease, linking diet with these conditions. Here we demonstrate that in mice episodic memory, together with spatial and contextual associative memory, is compromised after only one day of high-fat diet. However, novel object recognition memory remains intact. This shows not only a more rapid effect than previously reported but also that complex memories are at high risk of being compromised by a high-fat diet. In addition, we show that these memory deficits are rapidly reversed by switching mice from a high-fat diet back to a low-fat diet. These findings have important implications for the contribution of nutrition to the development of cognitive decline and Alzheimer's disease.