The Red Sea sponge Hemimycale arabica afforded the known (Z)-5-(4-hydroxybenzylidene)-hydantoin (1). This natural phenylmethylene hydantoin (PMH) 1 and the synthetic (Z)-5-(4-(ethylthio)benzylidene)-hydantoin (2) showed potent in vitro and in vivo anti-growth and anti-invasive properties against PC-3M prostate cancer cells in MTT, spheroid disaggregation, and in mice models. To explore a possible molecular target of PMHs, the most potent synthetic analogue 2 has been virtually screened against various protein kinases. Molecular modeling study has shown that 2 can be successfully docked within the binding pocket of glycogen synthase kinase-3beta (GSK-3beta) similar to the well-known GSK-3beta inhibitor I-5. Several PMHs showed potent in vitro GSK-3beta inhibitory activity with an IC(50) range of 4-20microM. The most potent analogue 3 showed a significant increase in liver glycogen level at the 5, 15, and 25mg/kg dose levels, in vivo. Pharmacophore model was built and validated using in-house database of active and inactive GSK-3beta inhibitors. The GSK-3beta inhibitory activity of PMHs entitles them to be potential leads for the treatment of cancer, Alzheimer's disease, bipolar disorders, stroke, different tau pathologies, and type-2 diabetes.