Recurrent use of existing genes through gene duplication or lateral transfer is the most common evolutionary mechanism to generate new protein-coding genes in bacteria (1,2). However, this leaves the question as to the origin of the primordial gene pool unanswered, and does not provide a comprehensive model for de novo creation of new protein sequences during the course of evolution. Rickettsia are rather unique in this context, uniquely exhibiting mobile palindromic repeats (RPEs) that are capable of creating new peptides (35-50 amino acids) by inserting themselves within protein-coding genes (3). The recurrent application of such a process, coupled with the accelerated evolution of the inserted peptides, might in fact account for bona fide genomic innovations (4,5). Given its potentially enormous evolu- tionary significance, it is paradoxical that this phenom- enon is not encountered in many other bacteria. However, the analysis of recently obtained Wolbachia genomes led to the identification of (i) RPEs and (ii) a new family of protein-coding palindromic repeats in these genomes, suggesting that this puzzling evolutionary process is also at work in Wolbachia.