The antibacterial activity of E colicin endonucleases (DNases) is counteracted by the binding of immunity proteins; the affinities of cognate and non-cognate complexes differing by up to ten orders of magnitude. Here, we address the mechanism of complex formation using a combination of protein engineering, pre-steady-state kinetics and isothermal titration calorimetry, in order to understand the underlying basis for specificity. Contrary to previous work, we show that a pre-equilibrium mechanism does not explain the binding kinetics. Instead, the data are best explained by a modified induced-fit mechanism where cognate and non-cognate complexes alike form a non-specific, conformationally dynamic encounter complex, most likely centred on conserved interactions at the interface. The dynamics appear to be an intrinsic property of the encounter complex where the proteins move relative to one another, thereby sampling different conformations rather than being "induced" by binding. This allows optimal alignment of interface specificity sites, without producing energetically costly conformational changes, essential for high-affinity binding. Importantly, specificity is achieved without slowing the rate of association, an important requirement for rapid inhibition of the colicin in the producing bacterial cell. A rigid-body rotation model is also consistent with the observation that specificity contacts in colicin-immunity protein complexes can involve different regions of the interface. Such a kinetic discrimination mechanism explains the ability of DNase-specific immunity proteins to display dual recognition specificity, wherein they are broadly cross-reactive yet are highly specific, achieving femtomolar binding affinities in complexes with their cognate DNases.