Objectives: Alzheimer’s disease (AD), an overwhelming neurodegenerative disease, has deleterious effects on the brain that consequently causes memory loss and language impairment. This study was intended to investigate the neuroprotective activity of the two essential oils (EOs) from Iranian Pistacia khinjuk (PK) leaves and Allium sativum (AS) cloves against β-Amyloid 25–35 (Aβ25-35) induced elevation of cholinesterase enzymes in AD. Methods: The EOs of PK (PKEO) and AS (ASEO) were prepared and analyzed in terms of extraction yield, phenolic content, and cholinergic markers in vitro. Moreover, both were administered orally to adult male Wistar rats at concentrations of 1, 2, and 3%. The inhibitory potential of PKEO and ASEO was compared with Donepezil (0.75 mg/kg) against the high activities of acetylcholinesterase (AChE) and butyrylcholinesterase (BChE) enzymes. Results: PKEO reached an inhibition rate of 83.6% and 81.4% against AChE and BChE, respectively. ASEO had lower anti-cholinesterase activity (65.4% and 31.5% for the inhibition AChE and BChE). PKEO was found to have more phenolic content than ASEO. A significantly positive correlation was observed between the total phenolics and anti-cholinesterase potential. In rats, both EOs decreased the enzyme activity in a concentration-dependent manner. As compared with Donepezil, the significant difference in the AChE and BChE inhibition occurred as rats were treated with PKEO 3% (p < 0.05). Conclusion: It could be concluded that PKEO and ASEO are potent inhibitors of AChE and BChE in rats that hold promise to be used for the treatment of AD.