Glycogen synthase kinase-3β (GSK-3β) represents a relevant drug target for the treatment of neurodegenerative pathologies including Alzheimer’s disease. We herein report on the optimization of a novel class of GSK-3β inhibitors based on the tofacitinib-derived screen hit 3-((3R,4R)-3-((7-chloro-9H-pyrimido[4,5-b]indol-4-yl)(methyl)amino)-4-methylpiperidin-1-yl)-3-oxopropanenitrile (1). We synthesized a series of 19 novel 7-chloro-9H-pyrimido[4,5-b]indole-based derivatives and studied their structure–activity relationships with focus on the cyanoacetyl piperidine moiety. We unveiled the crucial role of the nitrile group and its importance for the activity of this compound series. A successful rigidization approach afforded 3-(3aRS,7aSR)-(1-(7-chloro-9H-pyrimido[4,5-b]indol-4-yl)octahydro-6H-pyrrolo[2,3-c]pyridin-6-yl)-propanenitrile (24), which displayed an IC50 value of 130 nM on GSK-3β and was further characterized by its metabolic stability. Finally, we disclosed the putative binding modes of the most potent inhibitors within the ATP binding site of GSK-3β by 1 µs molecular dynamics simulations.