Terrestrial arthropods are commonly infected with maternally inherited bacterial symbionts that cause cytoplasmic incompatibility (CI). In CI, the outcome of crosses between symbiont-infected males and uninfected females is reproductive failure, increasing the relative fitness of infected females and leading to spread of the symbiont in the host population. CI symbionts have profound impacts on host genetic structure and ecology and may lead to speciation and the rapid evolution of sex determination systems. Cardinium hertigii, a member of the Bacteroidetes and symbiont of the parasitic wasp Encarsia pergandiella, is the only known bacterium other than the Alphaproteobacteria Wolbachia to cause CI. Here we report the genome sequence of Cardinium hertigii cEper1. Comparison with the genomes of CI-inducing Wolbachia pipientis strains wMel, wRi, and wPip provides a unique opportunity to pinpoint shared proteins mediating host cell interaction, including some candidate proteins for CI that have not previously been investigated. The genome of Cardinium lacks all major biosynthetic pathways but harbors a complete biotin biosynthesis pathway, suggesting a potential role for Cardinium in host nutrition. Cardinium lacks known protein secretion systems but encodes a putative phage-derived secretion system distantly related to the antifeeding prophage of the entomopathogen Serratia entomophila. Lastly, while Cardinium and Wolbachia genomes show only a functional overlap of proteins, they show no evidence of laterally transferred elements that would suggest common ancestry of CI in both lineages. Instead, comparative genomics suggests an independent evolution of CI in Cardinium and Wolbachia and provides a novel context for understanding the mechanistic basis of CI.