Inhibition of cholinesterases remains one of a few available treatment strategies for neurodegenerative dementias such as Alzheimer’s disease and related conditions. The current study was inspired by previous data on anticholinesterase properties of diterpenoids from Perovskia atriplicifolia and other Lamiaceae species. The acetylcholinesterase (AChE) and butyrylcholinesterase (BChE) inhibition by the three new natural compounds—(1R,15R)-1-acetoxycryptotanshinone (1), (1R)-1-acetoxytanshinone IIA (2), and (15R)-1-oxoaegyptinone A (3)—as well as, new for this genus, isograndifoliol (4) were assessed. Three of these compounds exhibited profound inhibition of butyrylcholinesterase (BChE) and much weaker inhibition of acetylcholinesterase (AChE). All compounds (1–4) selectively inhibited BChE (IC50 = 2.4, 7.9, 50.8, and 0.9 µM, respectively), whereas only compounds 3 and 4 moderately inhibited AChE (IC50 329.8 µM and 342.9 µM). Molecular docking and in silico toxicology prediction studies were also performed on the active compounds. Natural oxygenated norditerpenoids from the traditional Central Asian medicinal plant P. atriplicifolia are selective BChE inhibitors. Their high potential makes them useful candidate molecules for further investigation as lead compounds in the development of a natural drug against dementia caused by neurodegenerative diseases.