Substrate recognition and specificity are essential for the reliability and fidelity of protein kinase function. GSK-3 has a unique substrate specificity that requires prior phosphorylation of its substrates. However, how the enzyme selects its phosphorylated substrates is unknown. Here, we combined in silico modeling with mutagenesis and biological studies to identify GSK-3-substrate interaction sites located within its binding cleft. Protein-protein docking of GSK-3β and the phosphorylated cAMP responsive element binding protein (pCREB) (using the available experimentally determined structures), identified Phe67, Gln89, and Asn95 of GSK-3β as putative binding sites interacting with the CREB phosphorylation motif. Mutations of these residues to alanine impaired GSK-3β phosphorylation of several substrates, without abrogating its autocatalytic activity. Subsequently, expression of the GSK-3β mutants in cells resulted in decreased phosphorylation of substrates CREB, IRS-1, and β-catenin, and prevented their suppression of glycogen synthase activity as compared with cells expressing the wild-type GSK-3β. Our studies provide important additional understanding of how GSK-3β recognizes its substrates: In addition to prior phosphorylation typically required in GSK-3 substrates, substrate recognition involves interactions with GSK-3β residues: Phe67, Gln89, and Asn95, which confer a common basis for substrate binding and selectivity, yet allow for substrate diversity.