A detailed assessment of the evolution and phylogenetic utility of two genes, ftsZ and wsp, was used to investigate the origin of male-killing Wolbachia, previously isolated from the ladybird Adalia bipunctata and the butterfly Acraea encedon. The analysis included almost all available sequences of B-group Wolbachia and two outgroup taxa and showed that (1) the two gene regions differ in phylogenetic utility, (2) sequence variation is here correlated with phylogenetic information content, (3) both genes show significant rate heterogeneity between lineages, (4) increased substitution rates are associated with homoplasy in the data, (5) wsp sequences of some taxa appear to be subject to positive selection, and (6) only a limited number of clades can be inferred with confidence due to either lack of phylogenetic information or the presence of homoplasy. With respect to the evolution of male-killing, the two genes nevertheless seemed to provide unbiased information. However, they consistently produce contradictory results. Current data therefore do not permit clarification of the origin of this behavior. In addition, A. bipunctata was found to be a host to two recently diverged strains of male-killing Wolbachia that showed increased substitution rates for both genes. Moreover, the wsp gene, which codes for an outer membrane protein, was found to be subject to positive selection in these taxa. These findings were postulated to be the product of high selection pressures due to antagonistic host-symbiont interactions in this ladybird species. In conclusion, our study demonstrates that the results of a detailed phylogenetic analysis, including characterization of the limitations of such an approach, can serve as a valuable basis for an understanding of the evolution of Wolbachia bacteria. Moreover, particular features of gene evolution, such as elevated substitution rates or the presence of positive selection, may provide information about the dynamics of Wolbachia-host associations.