The role of different genotypes of apolipoprotein E (apoE) in the etiology of Alzheimer’s disease is widely recognized. It has been shown that altered functioning of apoE may promote 4-hydroxynonenal modification of mitochondrial proteins, which may result in mitochondrial dysfunction, aggravation of oxidative stress, and neurodegeneration. Mitochondrial aldehyde dehydrogenase (ALDH2) is an enzyme considered to perform protective function in mitochondria by the detoxification of the end products of lipid peroxidation, such as 4-hydroxynonenal and other reactive aldehydes. The goal of our study was to apply a differential proteomics approach in concert with molecular and morphological techniques to elucidate the changes in the frontal cortex and hippocampus of apolipoprotein E knockout (apoE−/−) mice upon treatment with Alda-1—a small molecular weight activator of ALDH2. Despite the lack of significant morphological changes in the brain of apoE−/− mice as compared to age-matched wild type animals, the proteomic and molecular approach revealed many changes in the expression of genes and proteins, indicating the impairment of energy metabolism, neuroplasticity, and neurogenesis in brains of apoE−/− mice. Importantly, prolonged treatment of apoE−/− mice with Alda-1 led to the beneficial changes in the expression of genes and proteins related to neuroplasticity and mitochondrial function. The pattern of alterations implies mitoprotective action of Alda-1, however, the accurate functional consequences of the revealed changes require further research.