Immunity proteins inhibit colicins, protein toxins released by bacteria during times of environmental stress, by binding and inactivating their cytotoxic domains. This protects the producing organism as it attempts to kill off competing bacteria. The cytotoxic domains of related colicins share a high degree of sequence identity, as do their corresponding immunity proteins, yet specificity and affinity are also high, with little non-cognate biological cross-protection evident under physiological conditions. We review recent work on DNase-specific immunity proteins, which shows that, although both cognate and non-cognate proteins can bind a single toxin, their affinities can differ by as much as 12 orders of magnitude. We have termed this mode of binding dual recognition, because the DNase-binding surface of an immunity protein is made up of two components, one conserved and the other variable. The strength of the binding interaction is dominated by the conserved residues, while neighbouring variable residues control specificity. Similar dual recognition systems may exist in other biological contexts, particularly where a protein must discriminate the right binding partner from numerous, structurally homologous alternatives.