Pseudomonas exotoxin A or “PE” is a 66 kD, highly potent, cytotoxic protein secreted by the bacterium Pseudomonas aeruginosa. Various forms of PE have been coupled to other proteins, such as antibodies, to generate therapeutically useful cytotoxin conjugates that selectively target cells of a desired phenotype (such as tumor cells). In the present invention, peptides spanning the sequence of an approximately 38 kD form of Pseudomonas exotoxin A protein were analyzed for the presence of immunogenic CD4+ T cell epitopes. Six immunogenic T cell epitopes were identified. Residues were identified within each epitope for introduction of targeted amino acid substitutions to reduce or prevent immunogenic T-cell responses in PE molecules which may be administered to a heterologous host.