The Red Sea sponge Hemimycale arabica afforded the known (Z)-5-(4-hydroxybenzylidene)-hydantoin (1), (R)-5-(4-hydroxybenzyl)hydantoin (2), and (Z)-5-((6-bromo-1H-indol-3-yl)methylene)-hydantoin (3). The natural phenylmethylene hydantoin (PMH) 1 and the synthetic (Z)-5-(4-(ethylthio)benzylidene)-hydantoin (4) showed potent in vitro anti-growth and anti-invasive properties against PC-3M prostate cancer cells in MTT and spheroid disaggregation assays. PMHs 1 and 4 also showed significant anti-invasive activities in orthotopic xenograft and transgenic mice models. To study the effect of electronic and lipophilic parameters on the activity, a wide array of several substituted aldehydes possessing electron-withdrawing (+sigma), lipophilic (+pi), electron-donating (-sigma), and less lipophilic substituents (-pi) were used to synthesize several PMHs. Few des-phenylmethylenehydantoins and 2-thiohydanoins were also synthesized and the anti-invasive activities of all compounds were evaluated. Comparative molecular field analysis (CoMFA) was then used to study the 3D QSAR. Predictive 3D QSAR model with conventional r(2) and cross validated coefficient (q(2)) values up to 0.910 and 0.651 were established. In conclusion, PMH is a novel antimetastatic lead class with potential to control metastatic prostate cancer.