How do intricate multi-residue features such as protein-protein interfaces evolve? To address this question, we evolved a new colicin-immunity binding interaction. We started with Im9, which inhibits its cognate DNase ColE9 at 10(-14) M affinity, and evolved it toward ColE7, which it inhibits promiscuously (Kd > 10(-8) M). Iterative rounds of random mutagenesis and selection toward higher affinity for ColE7, and selectivity (against ColE9 inhibition), led to an approximately 10(5)-fold increase in affinity and a 10(8)-fold increase in selectivity. Analysis of intermediates along the evolved variants revealed that changes in the binding configuration of the Im protein uncovered a latent set of interactions, thus providing the key to the rapid divergence of new Im7 variants. Overall, protein-protein interfaces seem to share the evolvability features of enzymes, that is, the exploitation of promiscuous interactions and alternative binding configurations via 'generalist' intermediates, and the key role of compensatory stabilizing mutations in facilitating the divergence of new functions.