Prostate cancer is a leading of cause of cancer related death in men. Despite intensive investment in improving early diagnosis, it often escapes timely detection. Mortality remains high in advanced stage prostate cancer where palliative care remains the only option. Effective strategies are therefore needed to prevent the occurrence and progression of the disease. Plant-derived compounds have been an important source of several clinically useful anti-cancer agents and offer an attractive approach against prostate cancer. We previously showed that the methanol extract of Maytenus royleanus (MEM) leaves and its fractions possess significant antioxidant activity with therapeutic potential against free-radical associated damages. The present study evaluated the anti-proliferative activity of MEM in the prostate cancer model system. Analysis of MEM and its various fractions revealed the presence of triterpenoids, flavonoids and tannins, conjugated to one or more polar groups and carbohydrate moieties. Further studies against known standards established the existence of caffeic acid and quercetin 3-rhamnoside in varying concentration in different MEM fractions. Time course analysis of MEM treated prostate cancer cells indicated significant decrease in cell viability, assessed by MTT and clonogenic survival assays. This was accompanied by G2 phase arrest of cell cycle, downregulation of cyclin/cdk network and increase in cdk inhibitors. MEM treated cells exhibited cleavage of Caspase-3 and PARP, and modulation of apoptotic proteins, establishing apoptosis as the primary mechanism of cell death. Notably MEM suppressed AR/PSA signaling both in prostate cancer cell cultures and in the in vivo model. Intraperitoneal injection of MEM (1.25 and 2.5 mg/ animal) to athymic nude mice implanted with androgen sensitive CWR22Rν1 cells showed significant inhibition in tumor growth and decreased serum PSA levels reciprocating in vitro findings. Taken together, our data suggest that MEM may be explored further for its potential therapeutic effects against prostate cancer progression in humans.