Nuclease E colicins that exert their cytotoxic activity through either non-specific DNase or specific rRNase action are inhibited by immunity proteins in a high affinity interaction that gives complete protection to the producing host cell from the deleterious effects of the toxin. Previous X-ray crystallographic analysis of these systems has revealed that in both cases, the immunity protein inhibitor forms its highly stable complex with the enzyme by binding as an exosite inhibitor-adjacent to, but not obscuring, the enzyme active site. The structures of the free E9 DNase domain and its complex with an ssDNA substrate now show that inhibition is achieved without deformation of the enzyme and by occlusion of a limited number of residues of the enzyme critical in recognition and binding of the substrate that are 3' to the cleaved scissile phosphodiester. No sequence or structural similarity is evident between the two classes of cytotoxic domain, and the heterodimer interfaces are also dissimilar. Thus, whilst these structures suggest the basis for specificity in each case, they give few indications as to the basis for the remarkably strong binding that is observed. Structural analyses of complexes bearing single site mutations in the immunity protein at the heterodimer interface reveal further differences. For the DNases, a largely plastic interface is suggested, where optimal binding may be achieved in part by rigid body adjustment in the relative positions of inhibitor and enzyme. For the rRNases, a large solvent-filled cavity is found at the immunity-enzyme interface, suggesting that other considerations, such as that arising from the entropy contribution from bound water molecules, may have greater significance in the determination of rRNase complex affinity than for the DNases.