Legionellaceae are intracellular bacteria known as important human pathogens. In the environment, they are mainly found in biofilms associated with amoebas. In contrast to the gammaproteobacterial family Enterobacteriaceae, which established a broad spectrum of symbioses with many insect taxa, the only instance of legionella-like symbiont has been reported from lice of the genus Polyplax. Here, we sequenced the complete genome of this symbiont and compared its main characteristics to other Legionella species and insect symbionts. Based on rigorous multigene phylogenetic analyses, we confirm this bacterium as a member of the genus Legionella and propose the name Candidatus Legionella polyplacis, sp.n. We show that the genome of Ca. Legionella polyplacis underwent massive degeneration, including considerable size reduction (529.746 bp, 484 protein coding genes) and a severe decrease in GC content (23%). We identify several possible constraints underlying the evolution of this bacterium. On one hand, Ca. Legionella polyplacis and the louse symbionts Riesia and Puchtella experienced convergent evolution, perhaps due to adaptation to similar hosts. On the other hand, some metabolic differences are likely to reflect different phylogenetic positions of the symbionts and hence availability of particular metabolic function in the ancestor. This is exemplified by different arrangements of thiamine metabolism in Ca. Legionella polyplacis and Riesia. Finally, horizontal gene transfer is shown to play a significant role in the adaptive and diversification process. Particularly, we show that Ca. L. polyplacis horizontally acquired a complete biotin operon (bioADCHFB) that likely assisted this bacterium when becoming an obligate mutualist.