Prostate cancer (PCa) is the second most common cancer in men, causing more than 300,000 deaths every year worldwide. Due to their superior cell-killing ability and the relative simplicity of their preparation, immunotoxin molecules have great potential in the clinical treatment of cancer, and several such molecules have been approved for clinical application. In this study, we adopted a relatively simple strategy based on a single-domain antibody (sdAb) and an improved exotoxin A (PE) toxin (PE24X7) to prepare a safer immunotoxin against prostate-specific membrane antigen (PSMA) for PCa treatment. The designed anti-PSMA immunotoxin, JVM-PE24X7, was conveniently prepared in its soluble form in an () system, avoiding the complex renaturation process needed for immunotoxin preparation by the conventional strategy. The product was very stable and showed a very strong ability to bind the PSMA receptor. Cytotoxicity assays showed that this molecule at a very low concentration could kill PSMA-positive PCa cells, with an EC value (concentration at which the cell viability decreased by 50%) of 15.3 pM against PSMA-positive LNCaP cells. Moreover, this molecule showed very good killing selectivity between PSMA-positive and PSMA-negative cells, with a selection ratio of more than 300-fold. Animal studies showed that this molecule at a very low dosage (5 × 0.5 mg/kg once every three days) completely inhibited the growth of PCa tumors, and the maximum tolerable dose (MTD) was more than 15 mg/kg, indicating its very potent tumor-treatment ability and a wide therapeutic window. Use of the new PE toxin, PE24X7, as the effector moiety significantly reduced off-target toxicity and improved the therapeutic window of the immunotoxin. The above results demonstrate that the designed anti-PSMA immunotoxin, JVM-PE24X7, has good application value for the treatment of PCa.