Horizontal gene transfer is an important mechanism for the evolution of microbial genomes, and many horizontal gene transfer events are facilitated by genomic islands (GIs). Until now, few reports have provided evidence for the co-evolution of horizontally transferred genes and their hosts. We obtained 17 groups of homologous GIs, all of which appear in 8 or more bacterial strains of the same species or genus. Using phylogenetic analyses, we found that the topological structure of a distance tree based on the proteins of each group of homologous GIs was consistent with that based on the complete proteomes of the hosts. This result clearly indicates that GIs and their bacterial hosts have co-evolved. In addition to presenting and providing evidence for a novel concept, i.e., the co-evolution of GIs and their bacterial hosts, we also describe a new and interesting detail for the phylogenetic analysis of horizontally transferred genes: consistent phylogenetic trees can be obtained by focusing on homologous GIs despite the commonly accepted theory that the phylogenies of horizontally transferred sequences and host organisms should be inconsistent.