Rhizochalinin (Rhiz) is a novel marine natural sphingolipid-like compound, which shows promising in vitro and in vivo activity in human castration-resistant prostate cancer. In the present study, a global proteome screening approach was applied to investigate molecular targets and biological processes affected by Rhiz in castration-resistant prostate cancer. Bioinformatical analysis of the data predicted an antimigratory effect of Rhiz on cancer cells. Validation of proteins involved in the cancer-associated processes, including cell migration and invasion, revealed downregulation of specific isoforms of stathmin and LASP1, as well as upregulation of Grp75, keratin 81, and precursor IL-1β by Rhiz. Functional analyses confirmed an antimigratory effect of Rhiz in PC-3 cells. Additionally, predicted ERK1/2 activation was confirmed by Western blotting analysis, and revealed prosurvival effects in Rhiz-treated prostate cancer cells indicating a potential mechanism of resistance. A combination of Rhiz with MEK/ERK inhibitors PD98059 (non-ATP competitive MEK1 inhibitor) and FR180204 (ATP-competitive ERK1/2 inhibitor) resulted in synergistic effects. This work provides further insights into the molecular mechanisms underlying Rhiz bioactivity. Furthermore, our research is exemplary for the ability of proteomics to predict drug targets and mode of action of natural anticancer agents.