The bacterial toxin colicin E9 is secreted by producing Escherichia coli cells with its 9.5 kDa inhibitor protein Im9 bound tightly to its 14.5 kDa C-terminal DNase domain. Double- and triple-resonance NMR spectra of the 24 kDa complex of uniformly 13C and 15N labeled Im9 bound to the unlabeled DNase domain have provided sufficient constraints for the solution structure of the bound Im9 to be determined. For the final ensemble of 20 structures, pairwise RMSDs for residues 3–84 were 0.76 ± 0.14 Å for the backbone atoms and 1.36 ± 0.15 Å for the heavy atoms. Representative solution structures of the free and bound Im9 are highly similar, with backbone and heavy atom RMSDs of 1.63 and 2.44 Å, respectively, for residues 4–83, suggesting that binding does not cause a major conformational change in Im9. The NMR studies have also allowed the DNase contact surface on Im9 to be investigated through changes in backbone chemical shifts and NOEs between the two proteins determined from comparisons of 1H–1H–13C NOESY-HSQC spectra with and without 13C decoupling. The NMR-defined interface agrees well with that determined in a recent X-ray structure analysis with the major difference being that a surface loop of Im9, which is at the interface, has a different conformation in the solution and crystal structures. Tyr54, a key residue on the interface, is shown to exhibit NMR characteristics indicative of slow rotational flipping. A mechanistic description of the influence binding of Im9 has on the dynamic behavior of E9 DNase, which is known to exist in two slowly interchanging conformers in solution, is proposed.