Loading capacity and drug leakage from vehicles during circulation in blood is a major concern when developing nanoparticle-based cell-targeted cytotoxics. To circumvent this potential issue it would be convenient the engineering of drugs as self-delivered nanoscale entities, devoid of any heterologous carriers. In this context, we have here engineered potent protein toxins, namely segments of the diphtheria toxin and the Pseudomonas aeruginosa exotoxin as self-assembling, self-delivered therapeutic materials targeted to CXCR4+ cancer stem cells. The systemic administration of both nanostructured drugs in a colorectal cancer xenograft mouse model promotes efficient and specific local destruction of target tumor tissues and a significant reduction of the tumor volume. This observation strongly supports the concept of intrinsically functional protein nanoparticles, which having a dual role as drug and carrier, are designed to be administered without the assistance of heterologous vehicles.