Paclitaxel (PTX) is one of the most successful antineoplastic drugs and is widely used for the treatment of many forms of advanced and refractory cancer. Unfortunately, various drawbacks including non-selective cytotoxicity, poor water solubility and low bioavailability limit its clinical use. The aim of this study was to characterize a novel colloidal system made up of the natural protein zein, that would be able to efficiently retain the anticancer compound and increase its pharmacological effects. In fact, zein has promising characteristics that render it a potential material to be used in drug delivery application. The influences of temperature, pH and serum incubation on the stability of these particles, entrapment efficiency of PTX and toxicity on different cancer cell lines were evaluated. The nanosystems containing PTX demonstrated suitable storage stability, and were not destabilized by temperatures of up to 50 °C, pH alterations, the freeze-drying process or serum proteins. The encapsulation of PTX did not destabilize the structure of the zein nanoparticles and a suitable drug entrapment efficiency resulted. PTX-loaded zein nanoparticles showed an increased toxicity on different cancer cell lines with respect to the free drug, confirming its potential application in preclinical and clinical investigations.