Nowadays, Alzheimer's disease is the most prevalent epiphenomenon of the aging population. Although soluble amyloid-β (Aβ) species (monomers, oligomers) are recognized triggers of the disease, no therapeutic approach is able to stop it. Herbal medicines are used to treat different diseases in many regions of the world. On the Balkan Peninsula, at the eastern Mediterranean Sea, and adjacent regions, Sideritis species are used as traditional medicine to prevent age-related problems in elderly. To evaluate this traditional knowledge in controlled experiments, we tested extracts of two commonly used Sideritis species, Sideritis euboea and Sideritis scardica, with regard to their effects on cognition in APP-transgenic and aged, non-transgenic C57Bl/6 mice. Additionally, histomorphological and biochemical changes associated with Aβ deposition and treatment were assessed. We found that daily oral treatment with Sideritis spp. extracts highly enhanced cognition in aged, non-transgenic as well as in APP-transgenic mice, an effect that was even more pronounced when extracts of both species were applied in combination. The treatment strongly reduced Aβ42 load in APP-transgenic mice, accompanied by increased phagocytic activity of microglia, and increased expression of the α-secretase ADAM10. Moreover, the treatment was able to fully rescue neuronal loss of APP-transgenic mice to normal levels as seen in non-transgenic controls. Having the traditional knowledge in mind, our results imply that treatment with Sideritis spp. extracts might be a potent, well-tolerated option for treating symptoms of cognitive impairment in elderly and with regard to Alzheimer's disease by affecting its most prominent hallmarks: Aβ pathology and cognitive decline.