Insect–microbe endosymbiotic associations are omnipresent in nature, wherein the symbiotic microbes often play pivotal biological roles for their host insects. In particular, insects utilizing nutritionally imbalanced food sources are dependent on specific microbial symbionts to compensate for the nutritional deficiency via provisioning of B vitamins in blood-feeding insects, such as tsetse flies, lice, and bedbugs. Bat flies of the family Nycteribiidae (Diptera) are blood-sucking ectoparasites of bats and shown to be associated with co-speciating bacterial endosymbiont “Candidatus Aschnera chinzeii,” although functional aspects of the microbial symbiosis have been totally unknown. In this study, we report the first complete genome sequence of Aschnera from the bristled bat fly Penicillidia jenynsii. The Aschnera genome consisted of a 748,020 bp circular chromosome and a 18,747 bp circular plasmid. The chromosome encoded 603 protein coding genes (including 3 pseudogenes), 33 transfer RNAs, and 1 copy of 16S/23S/5S ribosomal RNA operon. The plasmid contained 10 protein coding genes, whose biological function was elusive. The genome size, 0.77 Mbp, was drastically reduced in comparison with 4–6 Mbp genomes of free-living γ-proteobacteria. Accordingly, the Aschnera genome was devoid of many important functional genes, such as synthetic pathway genes for purines, pyrimidines, and essential amino acids. On the other hand, the Aschnera genome retained complete or near-complete synthetic pathway genes for biotin (vitamin B7), tetrahydrofolate (vitamin B9), riboflavin (vitamin B2), and pyridoxal 5'-phosphate (vitamin B6), suggesting that Aschnera provides these vitamins and cofactors that are deficient in the blood meal of the host bat fly. Similar retention patterns of the synthetic pathway genes for vitamins and cofactors were also observed in the endosymbiont genomes of other blood-sucking insects, such as Riesia of human lice, Arsenophonus of louse flies, and Wigglesworthia of tsetse flies, which may be either due to convergent evolution in the blood-sucking host insects or reflecting the genomic architecture of Arsenophonus-allied bacteria.