Gut-associated microbiota of ants include Rhizobiales bacteria with affiliation to the genus Bartonella. These bacteria may enable the ants to fix atmospheric nitrogen, but no genomes have been sequenced yet to test the hypothesis. Sequence reads from a member of the Rhizobiales were identified in the data collected in a genome project of the ant Harpegnathos saltator. We present an analysis of the closed 1.86 Mb genome of the ant-associated bacterium, for which we suggest the species name Candidatus Tokpelaia hoelldoblerii. A phylogenetic analysis reveals a relationship to Bartonella and Brucella, which infect mammals. Novel gene acquisitions include a gene for a putative extracellular protein of more than 6,000 amino acids secreted by the type I secretion system, which may be involved in attachment to the gut epithelium. No genes for nitrogen fixation could be identified, but genes for a multi-subunit urease protein complex are present in the genome. The urease genes are also present in Brucella, which has a fecal-oral transmission pathway, but not in Bartonella, which use blood-borne transmission pathways. We hypothesize that the gain and loss of the urease function is related to transmission strategies and lifestyle changes in the host-associated members of the Rhizobiales.