Prostate cancer (PC) is the most frequently diagnosed disease in men in the United States. Curcumin (CUR), a natural diphenol, has shown potent anti-cancer efficacy in various types of cancers. However, suboptimal pharmacokinetics and poor bioavailability limit its effective use in cancer therapeutics. Several successful CUR nanoformulations have recently been reported which improve upon these features; however, there is no personalized safe nanoformulation for prostate cancer. This study contributes two important scientific aspects of prostate cancer therapeutics. The first objective was to investigate the comparative cellular uptake and cytotoxicity evaluation of β-cyclodextrin (CD), hydroxypropyl methylcellulose (cellulose), poly(lactic-co-glycolic acid) (PLGA), magnetic nanoparticles (MNP), and dendrimer based CUR nanoformulations in prostate cancer cells. Curcumin loaded cellulose nanoparticles (cellulose-CUR) formulation exhibited the highest cellular uptake and caused maximum ultrastructural changes related to apoptosis (presence of vacuoles) in prostate cancer cells. Secondly, the anti-cancer potential of the cellulose-CUR formulation was evaluated in cell culture models using cell proliferation, colony formation and apoptosis (7-AAD staining) assays. In these assays, the cellulose-CUR formulation showed improved anti-cancer efficacy compared to free curcumin. Our study shows, for the first time, the feasibility of cellulose-CUR formulation and its potential use in prostate cancer therapy.