Background: The evolutionary importance of horizontal gene transfer (HGT) from Wolbachia endosymbiotic bacteria to their eukaryotic hosts is a topic of considerable interest and debate. Recent transfers of genome fragments from Wolbachia into insect chromosomes have been reported, but it has been argued that these fragments may be on an evolutionary trajectory to degradation and loss. Results: We have discovered a case of HGT, involving two adjacent genes, between the genomes of Wolbachia and the currently Wolbachia-uninfected mosquito Aedes aegypti, an important human disease vector. The lower level of sequence identity between Wolbachia and insect, the transcription of all the genes involved, and the fact that we have identified homologs of the two genes in another Aedes species (Ae. mascarensis), suggest that these genes are being expressed after an extended evolutionary period since horizontal transfer, and therefore that the transfer has functional significance. The association of these genes with Wolbachia prophage regions also provides a mechanism for the transfer. Conclusion: The data support the argument that HGT between Wolbachia endosymbiotic bacteria and their hosts has produced evolutionary innovation.