Anthrax toxin protective antigen (PrAg) forms a heptamer in which the binding site for lethal factor (LF) spans two adjacent monomers. This suggested that high cell-type specificity in tumor targeting could be obtained using monomers that generate functional LF-binding sites only through intermolecular complementation. We created PrAg mutants with mutations affecting different LF-binding subsites and containing either urokinase plasminogen activator (uPA) or matrix metalloproteinase (MMP) cleavage sites. Individually, these PrAg mutants had low toxicity as a result of impaired LF binding, but when administered together to uPA- and MMP-expressing tumor cells, they assembled into functional LF-binding heteroheptamers. The mixture of two complementing PrAg variants had greatly reduced toxicity in mice and was highly effective in the treatment of aggressive transplanted tumors of diverse origin. These results show that anthrax toxin, and by implication other multimeric toxins, offer excellent opportunities to introduce multiple-specificity determinants and thereby achieve high therapeutic indices.