Insertion sequences (ISs) are the simplest transposable elements and are widely distributed in bacteria. It has long been thought that IS excision rarely occurs in bacterial cells because most bacteria exhibit no end-joining activity to regenerate donor DNA after IS excision. Recently, however, we found that excision of IS629, an IS3 family member, occurs frequently in Escherichia coli O157. In this paper, we describe a protein IS-excision enhancer (IEE) that promotes IS629 excision from the O157 genome in an IS transposase-dependent manner. Various types of genomic deletions are also generated on IEE-mediated IS excision, and IEE promotes the excision of other IS3 family members and ISs from several other IS families. These data and the phylogeny of IEE homologues found in a broad range of bacteria suggest that IEE proteins have coevolved with IS elements and have pivotal roles in bacterial genome evolution by inducing IS removal and genomic deletion.