Dysregulation of glycogen synthase kinase (GSK-3β) is implicated in the pathophysiology of many diseases, including type-2 diabetes, stroke, Alzheimer’s, and others. A multistage virtual screening strategy designed so as to overcome known caveats arising from the considerable flexibility of GSK-3β yielded, from among compounds in our in-house database and two commercial databases, new GSK-3β inhibitors with novel scaffold structures. The two most potent and selective validated hits, a 2-anilino-5-phenyl-1,3,4-oxadiazole (24) and a phenylmethylene hydantoin (28), both exhibited nanomolar affinity and selectivity over CDK2 and were potent enough for direct in vivo validation. Both were able to cause significant increases in liver glycogen accumulation in dose-dependent fashion. One also exhibited excellent blood-brain barrier permeability, the other adequate for a lead compound. Analogues of the oxadiazole 24 were synthesized to experimentally corroborate or rule out ligand-bound structures arising from docking studies. SAR results supported one docking study among a number of alternatives.