Bacterial endosymbionts are widespread across several insect orders and are involved in interactions ranging from obligate mutualism to reproductive parasitism. Candidatus Blochmannia gen. nov. (Blochmannia) is an obligate bacterial associate of Camponotus and related ant genera (Hymenoptera: Formicidae). The occurrence of Blochmannia in all Camponotus species sampled from field populations and its maternal transmission to host offspring suggest that this bacterium is engaged in a long-term, stable association with its ant hosts. However, evidence for cospeciation in this system is equivocal because previous phylogenetic studies were based on limited gene sampling, lacked statistical analysis of congruence, and have even suggested host switching. We compared phylogenies of host genes (the nuclear EF-1alphaF2 and mitochondrial COI/II) and Blochmannia genes (16S ribosomal DNA [rDNA], groEL, gidA, and rpsB), totaling more than 7 kilobases for each of 16 Camponotus species. Each data set was analyzed using maximum likelihood and Bayesian phylogenetic reconstruction methods. We found minimal conflict among host and symbiont phylogenies, and the few areas of discordance occurred at deep nodes that were poorly supported by individual data sets. Concatenated protein-coding genes produced a very well-resolved tree that, based on the Shimodaira-Hasegawa test, did not conflict with any host or symbiont data set. Correlated rates of synonymous substitution (d(S)) along corresponding branches of host and symbiont phylogenies further supported the hypothesis of cospeciation. These findings indicate that Blochmannia-Camponotus symbiosis has been evolutionarily stable throughout tens of millions of years. Based on inferred divergence times among the ant hosts, we estimated rates of sequence evolution of Blochmannia to be approximately 0.0024 substitutions per site per million years (s/s/MY) for the 16S rDNA gene and approximately 0.1094 s/s/MY at synonymous positions of the genes sampled. These rates are several-fold higher than those for related bacteria Buchnera aphidicola and Escherichia coli. Phylogenetic congruence among Blochmannia genes indicates genome stability that typifies primary endosymbionts of insects.